제출 #129992

#제출 시각아이디문제언어결과실행 시간메모리
129992Adhyyan1252팀들 (IOI15_teams)C++11
0 / 100
4032 ms362380 KiB
#include "teams.h" #include<bits/stdc++.h> using namespace std; #define DEBUG true #define INF 1e7 int n; struct node{ node *l, *r; int sum; node(int v = 0){ l = r = NULL; sum = v; } node(node* L, node* R){ l = L; r = R; sum = L->sum + R->sum; } }; node* build(int s, int e){ if(s == e){ return new node(0); } int m = (s + e)/2; return new node(build(s, m), build(m+1, e)); } node* upd(node* i, int s, int e, int indx, int val){ if(s == e){ return new node(val); } int m = (s + e)/2; if(indx <= m) return new node(upd(i->l, s, m, indx, val), i->r); else return new node(i->l, upd(i->r, m+1, e, indx, val)); } int query(node* i, int s, int e, int l, int r){ if(l <= s && e <= r) return i->sum; if(s > e || s > r || e < l) return 0; int m = (s + e)/2; return query(i->l, s, m, l, r) + query(i->r, m+1, e, l, r); } vector<int> t, lazy; vector<node*> roots; void prop(int i, int s, int e){ if(lazy[i] == -1) return; if(s != e){ lazy[i*2] = lazy[i]; lazy[i*2+1] = lazy[i]; } if(lazy[i] == INF) t[i] = 0; else t[i] = query(roots[lazy[i]], 0, n-1, s, e); lazy[i] = -1; } int pro(int i, int s, int e, int indx, int rem, int k, node* pntr){ prop(i, s, e); //find count here cerr<<"PRO "<<s<<" "<<e<<" "<<indx<<" "<<rem<<" "<<k<<endl; if(e < indx) return 0; if(rem < 0) return 0; cout<<"PRN: "<<pntr<<endl; int v = pntr->sum - t[i]; cout<<" V: "<<v<<endl; if(v <= rem && s >= indx){ //mark them all lazy[i] = k; prop(i, s, e); return v; } int m = (s + e)/2; int done = pro(i*2, s, m, indx, rem, k, pntr->l); done += pro(i*2+1, m+1, e, indx, rem - done, k, pntr->r); t[i] = t[i*2] + t[i*2+1]; return done; } void clr(){ lazy[1] = INF; } void print(node* i, int s, int e){ if(s == e){ cerr<<" N: "<<i<<" "<<s<<" : "<<i->sum<<endl; return; } int m = (s + e)/2; print(i->l, s, m); print(i->r, m+1, e); } vector<pair<int, int> > a; void init(int N, int A[], int B[]) { cerr<<"INIT STARTED"<<endl; n = N; a.resize(n); for(int i = 0; i < n; i++){ a[i] = {B[i]-1, A[i]-1}; } sort(a.begin(), a.end()); vector<vector<int> > f(n); for(int i = 0; i < n; i++){ f[a[i].second].push_back(i); } t = vector<int>(4*n, 0); lazy = vector<int>(4*n, -1); node* beg = build(0, n-1); roots = vector<node*>(n); for(int i = 0; i < n; i++){ if(i)roots[i] = roots[i-1]; else roots[i] = beg; for(int u: f[i]){ roots[i] = upd(roots[i], 0, n-1, u, 1); } cerr<<"PRINITNG for "<<i<<endl; //print(roots[i], 0, n-1); } cerr<<"INIT ENDED"<<endl; } int can(int M, int K[]) { cerr<<"ASKED QUERIES "<<endl; vector<int> q(M); for(int i = 0; i < M; i++){ q[i] = K[i]; } sort(q.begin(), q.end()); clr(); bool bad = false; for(int u: q){ cerr<<"PRCESSED ONE "<<u<<endl; //need to find left indxe int lo = 0, hi = n-1, mid; while(lo < hi){ mid = (lo + hi)/2; if(a[mid].first >= u-1){ //its good hi = mid; }else{ lo = mid+1; } } mid = (lo + hi)/2; if(a[mid].first < u-1){ bad = true; break; } int done = pro(1, 0, n-1, mid, u, u-1, roots[u-1]); if(done < u) { bad = true; break; } } cerr<<" M ANS: "<<bad<<endl; return bad?0:1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...