# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106425 | 2019-04-18T11:23:42 Z | figter001 | Teams (IOI15_teams) | C++17 | 2546 ms | 193172 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); } } 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); pair<int,int> lst = {-1,-1}; for(int i=0;i<M;i++){ int st = upper_bound(p.begin(),p.end(),make_pair(K[i],(int)1e9)) - p.begin(); if(st == 0) return 0; int add = 0; if(lst.first != -1){ k = lst.second; l = K[i-1]; r = K[i] - 1; get(lst.first,1,n); add = k; } st--; st = p[st].first; st = idx[st]; k = K[i] + add; l = K[i]; r = n; lst = {st,k}; // cout << l << ' ' << r << ' ' << k << endl; // cout << k << ' '; get(st,1,n); // cout << k << endl; assert(k >= 0); if(k != 0) return 0; } return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2304 KB | Output is correct |
2 | Correct | 5 ms | 2304 KB | Output is correct |
3 | Correct | 4 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 | 5 ms | 2304 KB | Output is correct |
7 | Correct | 5 ms | 2304 KB | Output is correct |
8 | Correct | 4 ms | 2304 KB | Output is correct |
9 | Incorrect | 4 ms | 2304 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 124 ms | 39448 KB | Output is correct |
2 | Correct | 119 ms | 39416 KB | Output is correct |
3 | Correct | 127 ms | 39408 KB | Output is correct |
4 | Correct | 138 ms | 39552 KB | Output is correct |
5 | Correct | 69 ms | 39408 KB | Output is correct |
6 | Correct | 78 ms | 39424 KB | Output is correct |
7 | Incorrect | 65 ms | 39412 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 128 ms | 39508 KB | Output is correct |
2 | Correct | 123 ms | 39560 KB | Output is correct |
3 | Correct | 550 ms | 42464 KB | Output is correct |
4 | Correct | 185 ms | 39664 KB | Output is correct |
5 | Correct | 327 ms | 39536 KB | Output is correct |
6 | Correct | 169 ms | 39596 KB | Output is correct |
7 | Incorrect | 162 ms | 39632 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 876 ms | 187060 KB | Output is correct |
2 | Correct | 791 ms | 187104 KB | Output is correct |
3 | Correct | 2546 ms | 193172 KB | Output is correct |
4 | Correct | 871 ms | 187204 KB | Output is correct |
5 | Correct | 697 ms | 187200 KB | Output is correct |
6 | Correct | 542 ms | 187104 KB | Output is correct |
7 | Incorrect | 687 ms | 187156 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |