Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<vector>
- using namespace std;
- int T,K,Q,n,v[1001000],A,B,valmax;
- int lazy[5000100],val[5000100];
- vector <int> sol;
- inline void Build(int nod,int st,int dr)
- {
- if(st==dr)
- {
- val[nod]=v[st];
- lazy[nod]=0;
- return;
- }
- int mij=(st+dr)/2;
- Build(2*nod,st,mij);
- Build(2*nod+1,mij+1,dr);
- val[nod]=max(val[2*nod],val[2*nod+1]);
- lazy[nod]=0;
- }
- inline void Update(int nod,int st,int dr)
- {
- if(lazy[nod])
- {
- val[nod]+=lazy[nod];
- if(st!=dr)
- {
- lazy[2*nod]+=lazy[nod];
- lazy[2*nod+1]+=lazy[nod];
- }
- lazy[nod]=0;
- }
- if(A<=st && dr<=B)
- {
- val[nod]++;
- if(st!=dr)
- {
- lazy[2*nod]++;
- lazy[2*nod+1]++;
- }
- return;
- }
- int mij=(st+dr)/2;
- if(A<=mij)
- Update(2*nod,st,mij);
- if(mij+1<=B)
- Update(2*nod+1,mij+1,dr);
- val[nod]=max(val[2*nod],val[2*nod+1]);
- }
- inline void Query(int nod,int st,int dr)
- {
- if(lazy[nod])
- {
- val[nod]+=lazy[nod];
- if(st!=dr)
- {
- lazy[2*nod]+=lazy[nod];
- lazy[2*nod+1]+=lazy[nod];
- }
- lazy[nod]=0;
- }
- if(A<=st && dr<=B)
- {
- valmax=max(valmax,val[nod]);
- return;
- }
- int mij=(st+dr)/2;
- if(A<=mij)
- Query(2*nod,st,mij);
- if(mij+1<=B)
- Query(2*nod+1,mij+1,dr);
- }
- int main()
- {
- int t,i;
- vector <int>::iterator it;
- n=1000100;
- scanf("%d",&T);
- for(t=1;t<=T;t++)
- {
- scanf("%d %d",&K,&Q);
- for(i=1;i<=n;i++)
- v[i]=0;
- Build(1,1,n);
- for(i=1;i<=Q;i++)
- {
- scanf("%d %d",&A,&B);
- B--;
- valmax=0;
- Query(1,1,n);
- if(valmax<K)
- {
- sol.push_back(i);
- Update(1,1,n);
- }
- }
- printf("Case %d:\n",t);
- for(it=sol.begin();it!=sol.end();it++)
- printf("%d ",*it);
- printf("\n");
- sol.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement