# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106438 | 2019-04-18T12:39:17 Z | figter001 | Teams (IOI15_teams) | C++17 | 1384 ms | 193112 KB |
#include "teams.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int nax = 5e5+50; struct node{ int val,l,r; node(){ l = r = -1; val = 0; } }; vector<node> seg,tmp; int idx[nax],n,cnt,k,l,r; vector<pair<int,int>> p; void build(int n,int s , int e){ if(s == e){ seg[n].val = 0; return; } seg[n].l = cnt++; seg[n].r = cnt++; build(seg[n].l,s,(s+e)/2); build(seg[n].r,(s+e)/2+1,e); } int update(int n , int s , int e,int at){ if(s > at || e < at) return n; int newId = cnt++; seg[newId].val = seg[n].val; if(s == e){ seg[newId].val++; return newId; } seg[newId].l = update(seg[n].l,s,(s+e)/2,at); seg[newId].r = update(seg[n].r,(s+e)/2+1,e,at); seg[newId].val = seg[seg[newId].l].val + seg[seg[newId].r].val; return newId; } /*void get(int n,int s,int e){ assert(n != -1); if(l > r || s > r || e < l) return; if(s == e){ k -= min(k,seg[n].val); return; } int le = seg[n].l; int ri = seg[n].r; if(s >= l && e <= r){ if(seg[le].val <= k){ k -= seg[le].val; get(ri,(s+e)/2+1,e); }else{ get(le,s,(s+e)/2); } }else{ get(le,s,(s+e)/2); get(ri,(s+e)/2+1,e); } }*/ int get(int n,int s,int e){ if(s > r || e < l || l > r) return 0; if(s >= l && e <= r) return seg[n].val; int le = seg[n].l; int ri = seg[n].r; return get(le,s,(s+e)/2) + get(ri,(s+e)/2+1,e); } void init(int N, int A[], int B[]) { memset(idx,-1,sizeof(idx)); n = N; seg.resize(30*n); for(int i=0;i<n;i++){ p.push_back({A[i],B[i]}); assert(B[i] <= N); } cnt = 1; int lst = cnt; build(cnt++,1,n); sort(p.begin(),p.end()); for(int i=0;i<n;i++){ int a = p[i].first; int b = p[i].second; idx[a] = cnt; update(lst,1,n,b); lst = idx[a]; } } int can(int M, int K[]) { sort(K,K+M); int lst = -1; int add = 0; for(int i=0;i<M;i++){ int st = upper_bound(p.begin(),p.end(),make_pair(K[i],(int)1e9)) - p.begin(); assert(st <= p.size()); if(st == 0) return 0; st--; st = p[st].first; st = idx[st]; add += K[i]; l = K[i]; r = n; lst = st; // cout << add << ' '; // cout << l << ' ' << r << ' ' << add << ' ' << k << endl; // cout << add << ' ' << k << ' '; int have = get(st,1,n); // cout << have << endl; // cout << k << endl; if(add > have) return 0; if(i + 1 < M){ l = K[i]; r = K[i+1] - 1; int here = get(st,1,n); add -= min(here,K[i]); } } return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2304 KB | Output is correct |
2 | Correct | 4 ms | 2304 KB | Output is correct |
3 | Correct | 5 ms | 2304 KB | Output is correct |
4 | Correct | 4 ms | 2304 KB | Output is correct |
5 | Correct | 5 ms | 2304 KB | Output is correct |
6 | Correct | 4 ms | 2432 KB | Output is correct |
7 | Correct | 4 ms | 2304 KB | Output is correct |
8 | Correct | 5 ms | 2304 KB | Output is correct |
9 | Correct | 4 ms | 2304 KB | Output is correct |
10 | Incorrect | 4 ms | 2304 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 39408 KB | Output is correct |
2 | Correct | 122 ms | 39460 KB | Output is correct |
3 | Correct | 140 ms | 39408 KB | Output is correct |
4 | Correct | 132 ms | 39408 KB | Output is correct |
5 | Correct | 69 ms | 39536 KB | Output is correct |
6 | Correct | 65 ms | 39408 KB | Output is correct |
7 | Correct | 67 ms | 39408 KB | Output is correct |
8 | Correct | 71 ms | 39408 KB | Output is correct |
9 | Correct | 62 ms | 39408 KB | Output is correct |
10 | Correct | 57 ms | 40020 KB | Output is correct |
11 | Correct | 65 ms | 40120 KB | Output is correct |
12 | Correct | 58 ms | 40176 KB | Output is correct |
13 | Correct | 94 ms | 40416 KB | Output is correct |
14 | Correct | 76 ms | 40432 KB | Output is correct |
15 | Incorrect | 114 ms | 40600 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 39512 KB | Output is correct |
2 | Correct | 121 ms | 39536 KB | Output is correct |
3 | Correct | 252 ms | 42408 KB | Output is correct |
4 | Correct | 136 ms | 39408 KB | Output is correct |
5 | Correct | 124 ms | 39532 KB | Output is correct |
6 | Correct | 114 ms | 39572 KB | Output is correct |
7 | Correct | 76 ms | 39532 KB | Output is correct |
8 | Incorrect | 94 ms | 39532 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 815 ms | 187164 KB | Output is correct |
2 | Correct | 823 ms | 187136 KB | Output is correct |
3 | Correct | 1384 ms | 193112 KB | Output is correct |
4 | Correct | 880 ms | 187104 KB | Output is correct |
5 | Correct | 421 ms | 187104 KB | Output is correct |
6 | Correct | 458 ms | 187104 KB | Output is correct |
7 | Correct | 309 ms | 187232 KB | Output is correct |
8 | Incorrect | 415 ms | 187104 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |