| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1245990 | LittleOrange | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll big = 1e18;
struct dsu{
ll n,ans;
vector<ll> p,sm,cls;
array<vector<ll>,2> mi;
dsu(const vector<ll> &a):n(a.size()),ans(0),p(a.size(),-1),sm(a){
cls.resize(n);
iota(cls.begin(),cls.end());
mi[0].assign(n,big);
mi[1].assign(n,big);
for(ll i = 0;i<n;i++){
mi[i&1] = a[i];
}
}
ll g(ll i){
return p[i]<0?i:p[i]=g(p[i]);
}
ll cal(ll i){
return sm[i]-(p[i]&1)*mi[cls[i]&1][i];
}
void m(ll a, ll b){
a = g(a),b = g(b);
if(a==b)return;
ans -= cal(a)+cal(b);
if(p[a]>p[b]) swap(a,b);
sm[a] += sm[b];
mi[0][a] = min(mi[0][a],mi[0][b]);
mi[1][a] = min(mi[1][a],mi[1][b]);
cls[a] = min(cls[a],cls[b]);
p[a] += p[b];
p[b] = a;
ans += cal(a);
}
void upd(ll i, ll v){
ll typ = i&1;
i = g(i);
ans -= cal(i);
mi[typ^1][i] = min(mi[typ^1][i],v);
ans += cal(i);
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
ll n = w.size();
ll q = e.size();
ll tot = 0;
for(ll i : a) tot += i;
vector<pair<ll,ll>> v;
for(ll i = 0;i<n;i++) v.push_back({w[i],a[i]-b[i]});
sort(v.begin(),v.end());
vector<ll> h(n);
for(ll i = 0;i<n;i++) h[i] = v[i].second;
dsu d(h);
vector<pair<ll,ll>> u;
for(ll i = 0;i<n-1;i++) u.push_back({v[i+1].first-v[i].first,i});
for(ll i = 0;i<n-2;i++) u.push_back({v[i+2].first-v[i].first,-(i+1)});
sort(u.begin(),u.end());
vector<pair<ll,ll>> o;
o.push_back({0,0});
for(auto [dd,i] : u){
if(i<0){
d.upd(-i,h[-i]);
}else{
d.m(i,i+1);
}
o.push_back({dd,d.ans});
}
vector<ll> ret(q);
for(ll i = 0;i<q;i++){
ret[i] = tot-(*--lower_bound(o.begin(),o.end(),pair<ll,ll>((ll)e[i]+1,0ll))).second;
}
return ret;
}