| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209588 | anfi | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using int64 = long long;
#define pi pair<int64, int64>
#define artefak pair<pi, pi>
const int64 inf = -(1LL << 40);
const int64 mxn = (1 << 18);
int64 parent[4*mxn],sz[4*mxn],val[mxn*4][2],mx[mxn*4];
int64 find(int n){
return parent[n] == n ? n : parent[n] = find(parent[n]);
}
int64 hitung(int n){
if(sz[n]%2 == 0) return 0;
return max(val[n][n&1], mx[n]);
}
vector<int64> calculate_costs(vector<int> w,vector<int> a, vector<int> b, vector<int> e){
int n = w.size(), q = e.size();
if(n == 0){
return vector<int64>(q, 0);
}
int sigma_a = 0;
vector<artefak> item;
for(int i = 0;i < n; i++){
sigma_a += a[i];
item.push_back({{w[i], a[i]}, {b[i], b[i]-a[i]}});
}
sort(item.begin(), item.end());
vector<int64> ans(q, 0);
vector<pi> q1,q2,que;
for(int i = 0;i <n; i++){
parent[i] = i;
sz[i] = 1;
val[i][i&1] = item[i].se.se;
mx[i] = inf;
val[i][(i+1)&1] = inf;
}
for(int i = 0; i < n-1; i++) q1.push_back({w[i+1]-w[i], i});
for(int i = 1; i < n-1; i++) q2.push_back({w[i+1]-w[i-1], i});
sort(q1.begin(), q1.end());
sort(q2.begin(), q2.end());
for(int i = 0; i < q; i++){
que.push_back({e[i], i});
}
sort(que.begin(), que.end());
int idx = 0, idx1 = 0;
for(auto[d, i] : que){
while(idx < q1.size() && q1[idx].fi <= d){
int64 u = find(q1[idx].se), v = find(q1[idx].se+1);
sigma_a += hitung(u)+hitung(v);
parent[u] = v;
sz[v] += sz[u];
val[v][0] = max(val[v][0], val[u][0]);
val[v][1] = max(val[v][1], val[u][1]);
mx[v] = max(mx[v], mx[u]);
sigma_a -= hitung(u);
idx++;
}
while(idx1 < q2.size() && q2[idx1].fi <= d){
int64 u = find(q2[idx1].se);
sigma_a += hitung(u);
mx[u] = max(mx[u], b[q2[idx1].se]-a[q2[idx1].se]);
sigma_a -= hitung(u);
idx1++;
}
ans[i] = sigma_a;
}
return ans;
}