Submission #1128818
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct StarrySky{
static const int MAX_N = 1 << 22;
int datm[2*MAX_N],data[2*MAX_N],n;
StarrySky(){}
StarrySky(int n_){init(n_);}
void init(int n_){
n=1;
while(n<n_) n*=2;
for(int i=0;i<n*2;i++) datm[i]=data[i]=0;
}
void add(int a,int b,int x,int k,int l,int r){
if(r<=a||b<=l) return;
if(a<=l&&r<=b){
data[k]+=x;
return;
}
add(a,b,x,k*2+1,l,(l+r)/2);
add(a,b,x,k*2+2,(l+r)/2,r);
datm[k]=min(datm[k*2+1]+data[k*2+1],datm[k*2+2]+data[k*2+2]);
}
int query(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return INT_MAX;
if(a<=l&&r<=b) return datm[k]+data[k];
int vl=query(a,b,k*2+1,l,(l+r)/2);
int vr=query(a,b,k*2+2,(l+r)/2,r);
return min(vl,vr)+data[k];
}
void add(int a,int b,int x){
add(a,b,x,0,0,n);
}
int query(int a,int b){
return query(a,b,0,0,n);
}
};
signed main(){
int n,q;
cin>>n>>q;
StarrySky ss(n);
int s[q],t[q];
for(int i=0;i<q;i++){
cin>>s[i]>>t[i];
s[i]--;
ss.add(s[i],t[i],1);
}
//for(int i=0;i<n;i++) cout<<ss.query(i,i+1)<<endl;
//cout<<endl;
vector<int> ans;
for(int i=0;i<q;i++){
ss.add(s[i],t[i],-1);
//cout<<ss.query(0,n)<<endl;
if(ss.query(0,n)) ans.push_back(i);
ss.add(s[i],t[i],1);
}
cout<<ans.size()<<endl;
for(int i=0;i<(int)ans.size();i++) cout<<ans[i]+1<<endl;
return 0;
}
/*
verified on 2017/02/18
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E
*/
Submission Info
Submission Time |
|
Task |
B - ドキドキデート大作戦高橋君 |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1592 Byte |
Status |
AC |
Exec Time |
359 ms |
Memory |
23668 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
All |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
AC |
2 ms |
2304 KB |
subtask0_sample_02.txt |
AC |
2 ms |
2304 KB |
subtask0_sample_03.txt |
AC |
2 ms |
2304 KB |
subtask1_01.txt |
AC |
126 ms |
20992 KB |
subtask1_02.txt |
AC |
281 ms |
23668 KB |
subtask1_03.txt |
AC |
116 ms |
13184 KB |
subtask1_04.txt |
AC |
223 ms |
14328 KB |
subtask1_05.txt |
AC |
221 ms |
14328 KB |
subtask1_06.txt |
AC |
2 ms |
2304 KB |
subtask1_07.txt |
AC |
2 ms |
2304 KB |
subtask1_08.txt |
AC |
2 ms |
2304 KB |
subtask1_09.txt |
AC |
2 ms |
2304 KB |
subtask2_01.txt |
AC |
248 ms |
22900 KB |
subtask2_02.txt |
AC |
324 ms |
21876 KB |
subtask2_03.txt |
AC |
2 ms |
2304 KB |
subtask2_04.txt |
AC |
2 ms |
2304 KB |
subtask2_05.txt |
AC |
2 ms |
2304 KB |
subtask2_06.txt |
AC |
2 ms |
2304 KB |
subtask2_07.txt |
AC |
2 ms |
2304 KB |
subtask2_08.txt |
AC |
359 ms |
15220 KB |