Submission #1215949

#TimeUsernameProblemLanguageResultExecution timeMemory
1215949hengliaoNile (IOI24_nile)C++20
32 / 100
60 ms15032 KiB
#include "nile.h" #include<bits/stdc++.h> using namespace std; #define F first #define S second #define pll pair<ll, ll> #define vll vector<ll> #define pb push_back typedef long long ll; namespace{ const ll mxN=1e5+5; const ll inf=1e18; ll dsu[mxN], mn[mxN][2], lef[mxN], rig[mxN]; ll ans; void add(ll tar){ ll siz=abs(dsu[tar]); if(siz%2==1){ ans+=mn[tar][lef[tar]&1]; } } void era(ll tar){ ll siz=abs(dsu[tar]); if(siz%2==1){ ans-=mn[tar][lef[tar]&1]; } } ll find_set(ll tar){ if(dsu[tar]<0) return tar; return dsu[tar]=find_set(dsu[tar]); } void unite(ll a, ll b){ ll f=find_set(a); ll s=find_set(b); if(abs(dsu[f])<abs(dsu[s])) swap(f, s); era(f); era(s); dsu[f]+=dsu[s]; mn[f][0]=min(mn[f][0], mn[s][0]); mn[f][1]=min(mn[f][1], mn[s][1]); lef[f]=min(lef[f], lef[s]); rig[f]=max(rig[f], rig[s]); dsu[s]=f; add(f); } } vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { memset(dsu, -1, sizeof(dsu)); ll n=W.size(); ll q=E.size(); vll w(n), a(n), b(n); vll ord(n); for(ll i=0;i<n;i++){ ord[i]=i; } auto compare=[&](ll x, ll y){ return W[x]<W[y]; }; sort(ord.begin(), ord.end(), compare); for(ll i=0;i<n;i++){ w[i]=W[ord[i]]; a[i]=A[ord[i]]; b[i]=B[ord[i]]; } vector<array<ll, 2>> edges; ans=0; for(ll i=0;i<n;i++){ ans+=a[i]; for(ll j=0;j<2;j++){ mn[i][j]=inf; } mn[i][i&1]=a[i]-b[i]; lef[i]=i; rig[i]=i; if(i<n-1) edges.pb({w[i+1]-w[i], i}); } vector<array<ll, 2>> qry; for(ll i=0;i<q;i++){ qry.pb({E[i], i}); } sort(qry.begin(), qry.end()); sort(edges.begin(), edges.end()); vll re(q); ll pt=0; for(auto &[x, y]:qry){ while(pt<(ll) edges.size() && edges[pt][0]<=x){ if(find_set(edges[pt][1])!=find_set(edges[pt][1]+1)){ unite(edges[pt][1], edges[pt][1]+1); } pt++; } re[y]=ans; } return re; }
#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...