제출 #1237271

#제출 시각아이디문제언어결과실행 시간메모리
1237271denislavSails (IOI07_sails)C++20
40 / 100
1096 ms7028 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; while(left>0) { int pos=query(1,from).pos; int to=min(pos+left-1,from); perform(pos,to); left-=(to-pos+1); from=pos-1; //cout<<i<<":"<<pos<<" "<<to<<"\n"; } } 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...