Submission #1215943

#TimeUsernameProblemLanguageResultExecution timeMemory
1215943hengliaoNile (IOI24_nile)C++20
38 / 100
59 ms12728 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; ll dsu[mxN], mn[mxN]; ll ans; void add(ll tar){ ll siz=abs(dsu[tar]); if(siz%2==1){ ans+=mn[tar]; } } void era(ll tar){ ll siz=abs(dsu[tar]); if(siz%2==1){ ans-=mn[tar]; } } 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]=min(mn[f], mn[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; for(ll i=0;i<n;i++){ ans+=a[i]; mn[i]=a[i]-b[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...