| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 377076 | ansol4328 | Sails (IOI07_sails) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>#define F first#define S secondusing namespace std;typedef long long ll;typedef pair<int,int> P;int n;P m[100005];int A[100005];bool in[100005];set<int> St;int main(){ scanf("%d",&n); for(int i=1 ; i<=n ; i++) scanf("%d %d",&m[i].F,&m[i].S); sort(m+1,m+1+n); int H=m[n].F; St.insert(H+1); in[H+1]=true; A[H+1]=-1; for(int i=1 ; i<=n ; i++){ int cur=H-m[i].F+1; if(m[i].F!=m[i-1].F){ int tmp=*(St.begin()); if(A[tmp]==0 && in[tmp]) St.erase(tmp), in[tmp]=false; St.insert(cur), in[cur]=true; } auto it=St.upper_bound(cur+m[i].S-1); int fn=*it; it--; int st=*it; if(fn!=cur+m[i].S){ int x=(fn-1)-(cur+m[i].S-1-st); // x~fn-1, cur~st-1 A[cur]++, A[st]--; A[x]++, A[fn]--; if(A[cur]==1 && !in[cur]) St.insert(cur), in[cur]=true; if(A[x]==1 && !in[x]) St.insert(x), in[x]=true; if(cur!=st && A[st]==0 && in[st]) St.erase(st), in[st]=false; if(A[fn]==0 && in[fn]) St.erase(fn), in[fn]=false; } else{ //cur~fn-1 A[cur]++; A[fn]--; if(A[cur]==1 && !in[cur]) St.insert(cur), in[cur]=true; if(A[fn]==0 && in[fn]) St.erase(fn), in[fn]=false; } } //calculating ll ans=0, v=0; for(int i=1 ; i<=H ; i++){ v+=A[i]; ans+=v*(v-1)/2LL; } printf("%lld",ans); return 0;}