Submission #1128583

#TimeUsernameProblemLanguageResultExecution timeMemory
1128583AverageAmogusEnjoyerSails (IOI07_sails)C++17
40 / 100
1096 ms5384 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; } template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; } mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int> ui(0, 1 << 30); int rng() { return ui(mrand); } const int N=100100; int n; struct S { int Min,l,r; }; S st[4*N]; int lz[4*N]; S op(S a,S b) { if (a.Min < b.Min) return a; if (a.Min > b.Min) return b; assert(a.r+1==b.l); return S{a.Min,a.l,b.r}; } void push(int u) { st[2*u].Min += lz[u],st[2*u+1].Min += lz[u]; lz[2*u]+=lz[u],lz[2*u+1]+=lz[u]; lz[u]=0; } void upd(int l,int r,int x,int u=1,int tl=0,int tr=N-1) { if (l > r) return; if (l == tl && r == tr) { st[u].Min += x; lz[u] += x; return; } push(u); int mid=(tl+tr)/2; upd(l,min(mid,r),x,2*u,tl,mid); upd(max(mid+1,l),r,x,2*u+1,mid+1,tr); st[u]=op(st[2*u],st[2*u+1]); } S query(int l,int r,int u=1,int tl=0,int tr=N-1) { if (l > r) return S{1<<30,0,0}; if (l == tl && r == tr) { return st[u]; } push(u); int mid=(tl+tr)/2; return op(query(l,min(mid,r),2*u,tl,mid),query(max(mid+1,l),r,2*u+1,mid+1,tr)); } void build(int u=1,int tl=0,int tr=N-1) { st[u]=S{0,tl,tr}; if (tl==tr) return; int mid=(tl+tr)/2; build(2*u,tl,mid); build(2*u+1,mid+1,tr); } int order[N]; int h[N],k[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i=0;i<n;i++) cin >> h[i] >> k[i]; iota(order,order+n,0); sort(order,order+n,[&](int i,int j) { return h[i] < h[j]; }); build(); for (int t=0;t<n;t++) { int i = order[t]; vector<pair<int,int>> to_do; // cout << i << endl; while(k[i] > 0) { S res = query(0,h[i] - 1); int l = res.l; int now = min(k[i],res.r-res.l+1); int r = l+now-1; to_do.emplace_back(l,r); k[i] -= now; upd(l,r,2*N); // cout << l << " " << r << endl; } for (auto &[l,r]: to_do) upd(l,r,-2*N+1); } ll ans = 0; for (int i=0;i<N;i++) { S Now = query(i,i); ans += 1LL * Now.Min * (Now.Min - 1) / 2; } cout << ans << endl; }
#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...