Submission #1237298

#TimeUsernameProblemLanguageResultExecution timeMemory
1237298denislavSails (IOI07_sails)C++20
0 / 100
644 ms7280 KiB
# include <iostream> # include <algorithm> using namespace std; const int MAX=1e5+11; int n,m=1e5; pair<int,int> a[MAX]; struct node { long long sum; int mn,pos; node friend operator + (node A, node B) { node res; res.sum=A.sum+B.sum; if(A.mn<=B.mn) { res.mn=A.mn; res.pos=A.pos; } else { res.mn=B.mn; res.pos=B.pos; } return res; } }; node tree[MAX*4]; long long lazy[MAX*4]; void build(int v=1, int l=1, int r=m) { if(l==r) { tree[v]={0,0,l}; return ; } int mid=(l+r)/2; build(v*2,l,mid); build(v*2+1,mid+1,r); tree[v]=tree[v*2]+tree[v*2+1]; } void push_lazy(int v, int l, int r) { if(lazy[v]==0) return ; tree[v].sum+=lazy[v]*(r-l+1); tree[v].mn+=lazy[v]; if(l!=r) { lazy[v*2]+=lazy[v]; lazy[v*2+1]+=lazy[v]; } lazy[v]=0; } void update(int le, int ri, int d, int v=1, int l=1, int r=m) { push_lazy(v,l,r); if(ri<l or r<le) return ; if(le<=l and r<=ri) { lazy[v]+=d; push_lazy(v,l,r); return ; } int mid=(l+r)/2; update(le,ri,d,v*2,l,mid); update(le,ri,d,v*2+1,mid+1,r); tree[v]=tree[v*2]+tree[v*2+1]; } node query(int le, int ri, int v=1, int l=1, int r=m) { push_lazy(v,l,r); if(ri<l or r<le) return {0,(int)1e9,(int)1e9}; if(le<=l and r<=ri) return tree[v]; int mid=(l+r)/2; return query(le,ri,v*2,l,mid)+query(le,ri,v*2+1,mid+1,r); } long long ans=0; void perform(int l, int r) { ans+=query(l,r).sum; update(l,r,1); //cout<<"->"<<l<<" "<<r<<"\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second; sort(a+1,a+n+1); build(); for(int i=1;i<=n;i++) { int from=a[i].first,left=a[i].second; node nd=query(1,from-left+1); int pos=nd.pos; int l=pos,r=from,pos2=pos; while(l<=r) { int mid=(l+r)/2; if(query(pos,mid).pos==pos) { pos2=mid; l=mid+1; } else r=mid-1; } //cout<<i<<":"<<pos<<" "<<pos2<<"\n"; if(pos2<=from) { perform(pos2,from); left-=from-pos2+1; } if(left>0) { perform(pos,pos+left-1); left=0; } } cout<<ans<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...