# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
73980 |
2018-08-29T13:08:48 Z |
edisonhello |
Teams (IOI15_teams) |
C++14 |
|
4000 ms |
338488 KB |
// #include"teams.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int v;
node():l(0),r(0),v(0){}
} *root[500005],pool[500005*25];
node *gn(node *ref=0){
static int ptr=-1; ++ptr;
if(ref){
pool[ptr].l=ref->l;
pool[ptr].r=ref->r;
pool[ptr].v=ref->v;
}
return &pool[ptr];
}
int n;
pair<int,int> p[500005];
#define mid ((l+r)>>1)
void build(node *now,int l,int r){
if(l==r)return;
build(now->l=gn(),l,mid);
build(now->r=gn(),mid+1,r);
}
void modify(node *now,int l,int r,int x){
++now->v;
if(l==r){ return; }
if(x<=mid)modify(now->l=gn(now->l),l,mid,x);
else modify(now->r=gn(now->r),mid+1,r,x);
}
int query(node *nl,node *nr,int l,int r,int ql,int qr){
if(r<ql || qr<l)return 0;
// cout<<"query range "<<l<<" to "<<r<<" cur v: "<<nl->v<<" and "<<nr->v<<endl;
if(ql<=l&&r<=qr)return nr->v-nl->v;
return query(nl->l,nr->l,l,mid,ql,qr)+query(nl->r,nr->r,mid+1,r,ql,qr);
}
void init(int _n,int _a[],int _b[]){
n=_n;
for(int i=0;i<n;++i)p[i+1]={_a[i],_b[i]};
sort(p+1,p+n+1);
build(root[0]=gn(),1,n);
int ptr=1;
for(int i=1;i<=n;++i){
root[i]=gn(root[i-1]);
while(ptr<=n && p[ptr].first<=i)modify(root[i]=gn(root[i]),1,n,p[ptr].second),++ptr;
}
}
namespace naive{
struct node{
node *l,*r;
int sz,pri,val;
int lz(){ return l?l->sz:0; }
int rz(){ return r?r->sz:0; }
void pull(){ sz=lz()+rz()+1; }
node(int v):l(0),r(0),sz(1),pri(rand()),val(v){}
} *root;
node *merge(node *a,node *b){
if(!a)return b; if(!b)return a;
if(a->pri>b->pri){
a->r=merge(a->r,b);
a->pull();
return a;
}
else{
b->l=merge(a,b->l);
b->pull();
return b;
}
}
void split_val(node *now,int val,node *&a,node *&b){
if(!now){ a=b=0; return; }
if(now->val<=val){
a=now;
split_val(now->r,val,a->r,b);
a->pull();
}
else{
b=now;
split_val(now->l,val,a,b->l);
b->pull();
}
}
void split_sz(node *now,int sz,node *&a,node *&b){
if(!now){ a=b=0; return; }
if(now->lz()>=sz){
b=now;
split_sz(now->l,sz,a,b->l);
b->pull();
}
else{
a=now;
split_sz(now->r,sz-1-now->lz(),a->r,b);
a->pull();
}
}
void del(node *&now){
if(!now)return;
del(now->l); del(now->r);
delete now;
now=0;
}
int solve(int m,int k[]){
int ptr=1;
for(int i=0;i<m;++i){
while(ptr<=n && p[ptr].first<=k[i]){
node *a,*b;
split_val(root,p[ptr].second,a,b);
root=merge(merge(a,new node(p[ptr].second)),b);
++ptr;
}
node *a,*b;
split_val(root,k[i]-1,a,b);
del(a);
if(!b || b->sz<k[i]){
del(b);
root=0;
return 0;
}
node *c,*d;
split_sz(b,k[i],c,d);
del(c);
root=d;
}
del(root);
return 1;
}
}
#define BOUND 500
int dp[BOUND+4];
int can(int m,int k[]){
sort(k,k+m);
// return naive::solve(m,k);
if(m>BOUND)return naive::solve(m,k);
else{
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<m;++i){
int mn=9897788;
for(int j=0;j<=i;++j){
if(j==0)mn=query(root[0],root[k[i]],1,n,k[i],n);
else mn=min(mn,dp[j-1]+query(root[k[j-1]],root[k[i]],1,n,k[i],n));
// cout<<"j: "<<j<<" , mn: "<<mn<<endl;
}
dp[i]=mn-k[i];
// cout<<"at "<<i<<" , dp: "<<dp[i]<<endl;
if(dp[i]<0)return 0;
}
return 1;
}
}
#ifdef WEAK
int l[500005],r[500005];
int main(){
int n; cin>>n;
for(int i=0;i<n;++i)cin>>l[i]>>r[i];
init(n,l,r);
int m; cin>>m; while(m--){
int k; cin>>k;
int *a=new int[k];
for(int i=0;i<k;++i)cin>>a[i];
cout<<can(k,a)<<endl;
}
}
#endif
Compilation message
teams.cpp: In function 'naive::node* naive::merge(naive::node*, naive::node*)':
teams.cpp:68:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(!a)return b; if(!b)return a;
^~
teams.cpp:68:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(!a)return b; if(!b)return a;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
240 ms |
293884 KB |
Output is correct |
2 |
Correct |
232 ms |
294056 KB |
Output is correct |
3 |
Correct |
238 ms |
294056 KB |
Output is correct |
4 |
Correct |
241 ms |
294056 KB |
Output is correct |
5 |
Correct |
247 ms |
294056 KB |
Output is correct |
6 |
Correct |
249 ms |
294056 KB |
Output is correct |
7 |
Correct |
264 ms |
294056 KB |
Output is correct |
8 |
Correct |
236 ms |
294056 KB |
Output is correct |
9 |
Correct |
240 ms |
294056 KB |
Output is correct |
10 |
Correct |
242 ms |
294056 KB |
Output is correct |
11 |
Correct |
227 ms |
294128 KB |
Output is correct |
12 |
Correct |
241 ms |
294128 KB |
Output is correct |
13 |
Correct |
238 ms |
294128 KB |
Output is correct |
14 |
Correct |
247 ms |
294128 KB |
Output is correct |
15 |
Correct |
246 ms |
294128 KB |
Output is correct |
16 |
Correct |
244 ms |
294128 KB |
Output is correct |
17 |
Correct |
250 ms |
294128 KB |
Output is correct |
18 |
Correct |
252 ms |
294160 KB |
Output is correct |
19 |
Correct |
238 ms |
294228 KB |
Output is correct |
20 |
Correct |
250 ms |
294228 KB |
Output is correct |
21 |
Correct |
264 ms |
294228 KB |
Output is correct |
22 |
Correct |
285 ms |
294228 KB |
Output is correct |
23 |
Correct |
270 ms |
294228 KB |
Output is correct |
24 |
Correct |
243 ms |
294228 KB |
Output is correct |
25 |
Correct |
281 ms |
294228 KB |
Output is correct |
26 |
Correct |
249 ms |
294228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
344 ms |
296456 KB |
Output is correct |
2 |
Correct |
304 ms |
296556 KB |
Output is correct |
3 |
Correct |
320 ms |
296556 KB |
Output is correct |
4 |
Correct |
294 ms |
296940 KB |
Output is correct |
5 |
Correct |
335 ms |
296940 KB |
Output is correct |
6 |
Correct |
266 ms |
296940 KB |
Output is correct |
7 |
Correct |
275 ms |
296940 KB |
Output is correct |
8 |
Correct |
284 ms |
296940 KB |
Output is correct |
9 |
Correct |
286 ms |
301356 KB |
Output is correct |
10 |
Correct |
284 ms |
301356 KB |
Output is correct |
11 |
Correct |
282 ms |
301356 KB |
Output is correct |
12 |
Correct |
257 ms |
301356 KB |
Output is correct |
13 |
Correct |
251 ms |
301356 KB |
Output is correct |
14 |
Correct |
255 ms |
301356 KB |
Output is correct |
15 |
Correct |
283 ms |
301356 KB |
Output is correct |
16 |
Correct |
272 ms |
301356 KB |
Output is correct |
17 |
Correct |
239 ms |
301356 KB |
Output is correct |
18 |
Correct |
278 ms |
301356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
289 ms |
301356 KB |
Output is correct |
2 |
Correct |
336 ms |
301356 KB |
Output is correct |
3 |
Correct |
456 ms |
301356 KB |
Output is correct |
4 |
Correct |
279 ms |
301356 KB |
Output is correct |
5 |
Correct |
3381 ms |
301356 KB |
Output is correct |
6 |
Correct |
2784 ms |
301464 KB |
Output is correct |
7 |
Correct |
276 ms |
302348 KB |
Output is correct |
8 |
Correct |
2003 ms |
303600 KB |
Output is correct |
9 |
Correct |
280 ms |
308828 KB |
Output is correct |
10 |
Correct |
411 ms |
309872 KB |
Output is correct |
11 |
Correct |
1543 ms |
310580 KB |
Output is correct |
12 |
Correct |
1554 ms |
310580 KB |
Output is correct |
13 |
Correct |
618 ms |
310580 KB |
Output is correct |
14 |
Correct |
585 ms |
311920 KB |
Output is correct |
15 |
Correct |
412 ms |
311992 KB |
Output is correct |
16 |
Correct |
395 ms |
313444 KB |
Output is correct |
17 |
Correct |
478 ms |
314844 KB |
Output is correct |
18 |
Correct |
482 ms |
316188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
833 ms |
325944 KB |
Output is correct |
2 |
Correct |
828 ms |
326104 KB |
Output is correct |
3 |
Correct |
1409 ms |
333336 KB |
Output is correct |
4 |
Correct |
838 ms |
334644 KB |
Output is correct |
5 |
Execution timed out |
4046 ms |
338488 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |