# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106406 | 2019-04-18T10:55:14 Z | figter001 | Teams (IOI15_teams) | C++17 | 2308 ms | 193076 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; } if(s >= l && e <= r){ int le = seg[n].l; int ri = seg[n].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(seg[n].l,s,(s+e)/2); get(seg[n].r,(s+e)/2+1,e); } } void init(int N, int A[], int B[]) { n = N; seg.resize(30*n); for(int i=0;i<n;i++){ p.push_back({A[i],B[i]}); } 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,0}; 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; // cout << i << endl; 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 << ' '; // cout << l << ' ' << r << ' ' << k << endl; get(st,1,n); // cout << k << endl; if(k != 0) return 0; } return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 4 ms | 384 KB | Output is correct |
9 | Incorrect | 2 ms | 384 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 123 ms | 37612 KB | Output is correct |
2 | Correct | 120 ms | 37712 KB | Output is correct |
3 | Correct | 137 ms | 37640 KB | Output is correct |
4 | Correct | 132 ms | 37868 KB | Output is correct |
5 | Correct | 70 ms | 37488 KB | Output is correct |
6 | Correct | 66 ms | 37488 KB | Output is correct |
7 | Incorrect | 67 ms | 37496 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 121 ms | 37936 KB | Output is correct |
2 | Correct | 143 ms | 37888 KB | Output is correct |
3 | Correct | 593 ms | 40864 KB | Output is correct |
4 | Correct | 196 ms | 37920 KB | Output is correct |
5 | Correct | 184 ms | 37596 KB | Output is correct |
6 | Correct | 167 ms | 37568 KB | Output is correct |
7 | Incorrect | 179 ms | 37488 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 918 ms | 187216 KB | Output is correct |
2 | Correct | 800 ms | 187100 KB | Output is correct |
3 | Correct | 2308 ms | 193076 KB | Output is correct |
4 | Correct | 747 ms | 187104 KB | Output is correct |
5 | Correct | 829 ms | 185184 KB | Output is correct |
6 | Correct | 651 ms | 185184 KB | Output is correct |
7 | Incorrect | 708 ms | 185128 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |