Submission #1239382

#TimeUsernameProblemLanguageResultExecution timeMemory
1239382MarwenElarbiNile (IOI24_nile)C++20
0 / 100
36 ms11844 KiB
#include <bits/stdc++.h> #include "nile.h" using namespace std; const int nax=1e5+5; #define fi first #define se second #define pb push_back int n,q; int parent[nax]; long long p[nax]; long long imp[nax]; long long sz[nax]; long long mn[nax]; int find(int x){ if(parent[x]==x) return x; return parent[x]=find(parent[x]); } bool sameset(int x,int y){ return find(x)==find(y); } long long ans=0; void joinset(int x,int y){ x=find(x); y=find(y); if(sz[x]%2) ans-=min(mn[x],(x%2 ? imp[x] : p[x])); if(sz[y]%2) ans-=min(mn[y],(y%2 ? imp[y] : p[y])); p[x]=min(p[x],p[y]); imp[x]=min(imp[x],imp[y]); mn[x]=min(mn[x],mn[y]); sz[x]+=sz[y]; if(sz[x]%2) ans+=min(mn[x],(x%2 ? imp[x] : p[x])); parent[y]=x; return; } std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { n=W.size();q=E.size(); vector<pair<int,pair<int,int>>> sorter(n); for (int i = 0; i < n; ++i) sorter[i]={W[i],{B[i],A[i]}}; sort(sorter.begin(),sorter.end()); for (int i = 0; i < n; ++i) { parent[i]=i; sz[i]=1; mn[i]=1e9; W[i]=sorter[i].fi; B[i]=sorter[i].se.fi; A[i]=sorter[i].se.se; if(i%2==0){ imp[i]=1e9; p[i]=A[i]-B[i]; }else{ imp[i]=A[i]-B[i]; p[i]=1e9; } ans+=A[i]; } vector<pair<long long,pair<int,int>>> tab; vector<long long> answer(q); for (int i = 0; i < n; ++i) { if(i<n-1) tab.push_back({W[i+1]-W[i],{i,i+1}}); if(i<n-2) tab.push_back({W[i+2]-W[i],{i,i+2}}); } sort(tab.begin(),tab.end()); vector<pair<long long,int>> query(q); for (int i = 0; i < q; ++i) query[i]={E[i],i}; sort(query.begin(),query.end()); int j=0; for(auto u:tab){ while(j<query.size()&&query[j].fi<u.fi){ answer[query[j++].se]=ans; } if(u.se.se-u.se.fi==1){ joinset(u.se.fi,u.se.se); }else{ if(sz[u.se.fi]%2) ans-= min(mn[u.se.fi],(u.se.fi%2 ? imp[u.se.fi] : p[u.se.fi])); mn[find(u.se.fi)]=min(mn[find(u.se.fi)],1ll*(A[u.se.fi+1]-B[u.se.fi+1])); if(sz[u.se.fi]%2) ans+= min(mn[u.se.fi],(u.se.fi%2 ? imp[u.se.fi] : p[u.se.fi])); } } return answer; }
#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...