| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65134 |
2018-08-06T17:10:14 Z |
edisonhello |
Sails (IOI07_sails) |
C++11 |
|
394 ms |
13984 KB |
#include<bits/stdc++.h>
using namespace std;
pair<int,int> fan[100005];
int n;
int cnt[100005];
long long ans=0;
struct node{
node *l,*r;
int sz,pri;
long long tag,val,tot;
int lz(){ return l?l->sz:0; }
int rz(){ return r?r->sz:0; }
void addtag(int d){ tag+=d; val+=d; tot+=1ll*d*sz; }
void push(){ if(l)l->addtag(tag); if(r)r->addtag(tag); tag=0; }
void pull(){ sz=lz()+rz()+1; tot=val+(l?l->tot:0ll)+(r?r->tot:0ll); }
node(long long val=0):l(0),r(0),sz(1),pri(rand()),tag(0),val(val),tot(val){}
} *root;
node *merge(node *a,node *b){
if(!a)return b; if(!b)return a;
a->push(); b->push();
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_sz(node *s,int sz,node *&a,node *&b){
if(!s){ a=b=0; return; }
s->push();
if(s->lz()>=sz){
b=s;
split_sz(s->l,sz,a,b->l);
b->pull();
}
else{
a=s;
split_sz(s->r,sz-1-s->lz(),a->r,b);
a->pull();
}
}
void split_val(node *s,int val,node *&a,node *&b){
if(!s){ a=b=0; return; }
s->push();
if(s->val<=val){
a=s;
split_val(s->r,val,a->r,b);
a->pull();
}
else{
b=s;
split_val(s->l,val,a,b->l);
b->pull();
}
}
int getR(node *now){
now->push();
if(!now->r)return now->val;
else return getR(now->r);
}
int getL(node *now){
now->push();
if(!now->l)return now->val;
else return getL(now->l);
}
void print(node *now){
if(!now)return;
now->push();
if(now->l)cout<<"(",print(now->l),cout<<")";
cout<<now->val;
if(now->r)cout<<"(",print(now->r),cout<<")";
}
int main(){
srand(time(0));
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
// n=10;
for(int i=0;i<n;++i){
cin>>fan[i].first>>fan[i].second;
// fan[i].first=rand()%20+1;
// fan[i].second=rand()%(fan[i].first+1);
}
sort(fan,fan+n);
int slots_open=0;
for(int i=0;i<n;++i){
while(slots_open<fan[i].first)root=merge(new node(0),root),++slots_open;
if(fan[i].second==0)continue;
// cout<<fan[i].first<<" "<<fan[i].second<<endl;
node *a,*b;
split_sz(root,fan[i].second,a,b);
ans+=a->tot;
a->addtag(1);
if(a && b){
int rrr=getR(a);
int lll=getL(b);
// cout<<"rrr lll "<<rrr<<" "<<lll<<endl;
if(rrr>lll){
node *c,*d,*e,*f;
split_val(a,rrr-1,c,d);
split_val(b,lll,e,f);
a=merge(c,e);
b=merge(d,f);
}
}
// print(a); cout<<" , "; print(b); cout<<endl;
root=merge(a,b);
// print(root); cout<<endl;
}
cout<<ans<<endl;
}
Compilation message
sails.cpp: In function 'node* merge(node*, node*)':
sails.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(!a)return b; if(!b)return a;
^~
sails.cpp:22: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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
660 KB |
Output is correct |
| 2 |
Correct |
3 ms |
660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
820 KB |
Output is correct |
| 2 |
Correct |
3 ms |
828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
828 KB |
Output is correct |
| 2 |
Correct |
4 ms |
836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1080 KB |
Output is correct |
| 2 |
Correct |
38 ms |
7132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
7132 KB |
Output is correct |
| 2 |
Correct |
75 ms |
7132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
7132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
7132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
9900 KB |
Output is correct |
| 2 |
Correct |
257 ms |
10776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
11848 KB |
Output is correct |
| 2 |
Correct |
213 ms |
11912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
394 ms |
13984 KB |
Output is correct |
| 2 |
Correct |
275 ms |
13984 KB |
Output is correct |
