Submission #1099751

#TimeUsernameProblemLanguageResultExecution timeMemory
1099751model_codeNile (IOI24_nile)C++17
100 / 100
91 ms16260 KiB
// model_solution/badawy_solution.cpp #include <bits/stdc++.h> using namespace std ; const int N = 1e5 + 10 ; int n,q; array<int, 3> arr[N]; int uni[N], sz[N], l[N], r[N], mn[N], mnp[N][2]; long long sum[N]; long long ans; int uni_find(int x) { return uni[x]=(uni[x]==x?x:uni_find(uni[x])); } long long calc(int x) { int a=l[x]; return sum[x] + (sz[x]%2 ? min({mn[x], mnp[x][a&1]}) : 0); } void unio(int x,int y) { x=uni_find(x); y=uni_find(y); if(x==y) return; ans-=calc(x); ans-=calc(y); sz[x]+=sz[y]; l[x]=min(l[x], l[y]); r[x]=max(r[x], r[y]); mn[x]=min({mn[x], mn[y]}); mnp[x][0]=min(mnp[x][0], mnp[y][0]); mnp[x][1]=min(mnp[x][1], mnp[y][1]); sum[x]+=sum[y]; uni[y]=x; ans+=calc(x); } vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { n=W.size(); q=E.size(); for(int i=0;i<n;i++) { arr[i]={W[i], A[i], B[i]}; } sort(arr,arr+n); for(int i=0;i<n;i++) { uni[i]=l[i]=r[i]=i; sz[i]=1; mn[i]=(1<<30); sum[i]=arr[i][2]-arr[i][1]; mnp[i][0]=mnp[i][1]=(1<<30); mnp[i][i&1] = -sum[i]; ans+=A[i]; } vector<array<int, 3> > eds; for(int i=0;i<n-1;i++) { eds.push_back({arr[i+1][0]-arr[i][0], -2, i}); if(i+2<n) eds.push_back({arr[i+2][0]-arr[i][0], -1, i}); } for(int i=0;i<q;i++) eds.push_back({E[i], 0, i}); sort(eds.begin(), eds.end()); vector<long long> ret(q); for(auto ed:eds) { if(ed[1]==0) ret[ed[2]]=ans; else if(ed[1]==-2) { unio(ed[2], ed[2]+1); } else { int x=uni_find(ed[2]), y=uni_find(ed[2]+2); assert(x==y); ans-=calc(x); int cost=arr[ed[2]+1][1] - arr[ed[2]+1][2]; mn[x]=min(mn[x], cost); ans+=calc(x); } } return ret; }
#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...