Submission #22026

#TimeUsernameProblemLanguageResultExecution timeMemory
22026sbansalcsTeams (IOI15_teams)C++14
Compilation error
0 ms0 KiB
//#include "teams.h" #include <stack> #include <math.h> #include <vector> #include <assert.h> #include <algorithm> #include <iostream> using namespace std; const int N = 5e5+5; #define right r #define left l #define mid (start+end)/2 struct node2; void err() { while (1) { } } struct node { node *l,*r; int val; node() { l=NULL,r=NULL,val=0; } node* build(int start, int end) { val=0; if(start!=end) { l=new node,r=new node,l=l->build(start,mid),r=r->build(mid+1,end); } return this; } int query(int start, int end, int a, int b) { if(start>=a && end<=b) return val; else if(start>b || end<a) return 0; else return l->query(start,mid,a,b)+r->query(mid+1,end,a,b); } node* update(int start, int end, int x, int v) { node* f=new node; f->left=left; f->right=right; f->val=val+v; if(start==end) { return f; } else if(x<=mid) { f->left=left->update(start,mid,x,v); } else { f->right=right->update(mid+1,end,x,v); } return f; } // int assign(node2* used, int start, int end, int a, int b, int v) { //// used=used->lz() // } }; node* points[N*4]; int val[N*4]; void build(int idx, int start, int end) { points[idx]=NULL; val[idx]=0; if(start!=end) { build(idx*2, start, mid); build(idx*2+1, mid+1, end); } } void clear(int idx, int start, int end) { if(val[idx]!=0 || points[idx]!=NULL) { if(start!=end) clear(idx*2,start,mid),clear(idx*2+1,mid+1,end); } val[idx]=0; points[idx]=NULL; } void lz(int idx,int start, int end) { if(points[idx]==NULL) return; val[idx]=points[idx]->val; if(start!=end) { points[idx*2]=points[idx]->l; points[idx*2+1]=points[idx]->r; } points[idx]=NULL; } //struct node2 //{ // node* points; // int val; // node2 *l,*r; // node2* build(int start, int end) { // val=0,points=NULL; // if(start!=end) { // l=new node2,r=new node2;l=l->build(start,mid),r=r->build(mid+1,end); // } // return this; // } // node2* clear(int start, int end) { // if(val!=0 || points!=NULL) { // if(start!=end) l=l->clear(start,mid),r=r->clear(mid+1,end); // } // points=NULL,val=0; // return this; // } // node2* lz(int start, int end) { // if(!points) return this; // val=points->val; // if(start!=end) { // l->points=points->l; // r->points=points->r; // } // points=NULL; // return this; // } //}; // // //node2* used; int assign(node* rt, int idx, int start, int end, int a, int b, int v) { if(rt==NULL) err(); // if(used==NULL) err(); // used=used->lz(start,end); lz(idx, start, end); if(start>b || end<a) return 0; if(v==0) return 0; int av =rt->val-val[idx]; if(start>=a && end<=b) { if(av<=v) { // used->points=rt; points[idx]=rt; lz(idx, start, end); return av; } else { if(start==end) return 0; int lf=assign(rt->l, idx*2, start, mid, a, b, v); int rf=assign(rt->r, idx*2+1, mid+1, end, a, b, v-lf); return rf+lf; } } else { if(start==end) return 0; int lf=assign(rt->l, idx*2, start, mid, a, b, v); int rf=assign(rt->r, idx*2+1, mid+1, end, a, b, v-lf); return rf+lf; } } node* root[N]; int A[N],B[N]; int n; int del[N]; int sz=0; int dp[N]; void init(int _n, int a[], int b[]) { n=_n; vector<pair<int,int>> vt; for(int i=1;i<=n;i++) { A[i]=a[i-1]; B[i]=b[i-1]; vt.push_back({A[i],B[i]}); } sort(vt.begin(),vt.end()); root[0]=new node;root[0]=root[0]->build(1,n); int preve=0; for(int i=0;i<n;i++) { while(preve+1<vt[i].first) { root[preve+1]=root[preve]; preve++; } root[vt[i].first]=root[preve]->update(1,n,vt[i].second,1); // assert(vt[i].first-preve<=1); preve=vt[i].first; } for(int i=preve+1;i<=n;i++) { root[i]=root[i-1]; } // used=new node2; // used=used->build(1, n); build(1, 1, n); } int getCount(int a, int b) { int h=root[b]->query(1,n,b,n)-root[a]->query(1,n,b,n); return h; } int can(int M, int K[]) { sort(K,K+M); int cnt=0; // used=used->clear(1, n); clear(1, 1, n); for (int i=0; i<M; i++) { cnt=assign(root[K[i]], 1, 1, n, K[i], n, K[i]); if(cnt<K[i]) return 0; // assert(cnt==K[i]); } return 1; } static inline int _readInt() { int x;scanf("%d",&x); return x; } int main() { int N; N = _readInt(); int *A = (int*)malloc(sizeof(int)*(unsigned int)N); int *B = (int*)malloc(sizeof(int)*(unsigned int)N); for (int i = 0; i < N; ++i) { A[i] = _readInt(); B[i] = _readInt(); } init(N, A, B); int Q; Q = _readInt(); for (int i = 0; i < Q; ++i) { int M; M = _readInt(); int *K = (int*)malloc(sizeof(int)*(unsigned int)M); for (int j = 0; j < M; ++j) { K[j] = _readInt(); } printf("%d\n", can(M, K)); } return 0; }

Compilation message (stderr)

teams.cpp: In function 'int main()':
teams.cpp:224:9: warning: declaration of 'N' shadows a global declaration [-Wshadow]
     int N;
         ^
teams.cpp:11:11: note: shadowed declaration is here
 const int N = 5e5+5;
           ^
teams.cpp:226:10: warning: declaration of 'A' shadows a global declaration [-Wshadow]
     int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
          ^
teams.cpp:163:5: note: shadowed declaration is here
 int A[N],B[N];
     ^
teams.cpp:227:10: warning: declaration of 'B' shadows a global declaration [-Wshadow]
     int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
          ^
teams.cpp:163:10: note: shadowed declaration is here
 int A[N],B[N];
          ^
teams.cpp: In function 'int _readInt()':
teams.cpp:219:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int x;scanf("%d",&x);
                         ^
/tmp/cc2t4zrR.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/ccy62reY.o:teams.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status