Submission #132562

#TimeUsernameProblemLanguageResultExecution timeMemory
132562someone_aaTeams (IOI15_teams)C++17
0 / 100
1677 ms524292 KiB
#include "teams.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 500100; // WARNING: SMALL N int n; class node { public: node *l, *r; int s; node(int _s) { s = _s; l = r = NULL; } node(node *lc, node *rc) { l = lc; r = rc; s = l -> s + r -> s; } }; vector<int>bs[maxn]; node *zero; node *build(int li=1, int ri=n) { if(li == ri) return zero; else { int mid = (li + ri) / 2; return new node(build(li, mid), build(mid+1, ri)); } } node *update(node *curr, int x, int li=1, int ri=n) { if(li == ri) { curr->s = curr->s + 1; return curr; } else { int mid = (li + ri) / 2; if(x <= mid) return new node(update(curr->l, x, li, mid), curr->r); else return new node(curr->l, update(curr->r, x, mid+1, ri)); } } // It creates new segment tree such that it takes the first d leafs from f_part // and the rest of the n - d are from s_part node *removefirst(int d, node *f_part, node *s_part, int li=1, int ri=n) { if(li > d) return s_part; else if(ri <= d) return f_part; if(li != ri) { int mid = (li + ri) / 2; return new node(removefirst(d, f_part->l, s_part->l, li, mid), removefirst(d, f_part->r, s_part->r, mid+1, ri)); } } // Takes the first k extra from available that are not in used node *mergeused(int k, node *available, node *used, int li=1, int ri=n) { if(li == ri) { return new node(used->s + k); } else { int mid = (li + ri) / 2; int l_part = available->l->s - used->l->s; if(l_part >= k) return new node(mergeused(k, available->l, used->l, li, mid), used->r); else return new node(available->l, mergeused(k - l_part, available->r, used->r, mid+1, ri)); } } node *emp; node *persistent_tree[maxn]; void init(int N, int A[], int B[]) { n = N; for(int i=0;i<n;i++) { bs[A[i]].pb(B[i]); } zero = new node(0); emp = build(); persistent_tree[0] = emp; for(int i=1;i<=n;i++) { persistent_tree[i] = persistent_tree[i-1]; persistent_tree[i] = removefirst(i-1, emp, persistent_tree[i]); // We don't care for the interavals starting before my position for(int j:bs[i]) { persistent_tree[i] = update(persistent_tree[i], j); } } } int can(int M, int K[]) { sort(K, K+M); node *used = emp; for(int i=0;i<M;i++) { used = removefirst(K[i]-1, emp, used); if(persistent_tree[K[i]]->s - used->s < K[i]) return 0; used = mergeused(K[i], persistent_tree[K[i]], used); } return 1; }

Compilation message (stderr)

teams.cpp: In function 'node* removefirst(int, node*, node*, int, int)':
teams.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...