| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1103837 | zNatsumi | Nile (IOI24_nile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
const int N = 1e5 + 5,
INF = 1e16;
int n, q, pa[N], sz[N], tot[N], odd_min[N], even_min[N], L[N], R[N], res = 0, answer[N];
ii que[N];
struct info{
int w, a, b;
info() {}
info(int w, int a, int b): w(w), a(a), b(b) {}
friend istream& operator >> (istream& is, info &rhs){
return is >> rhs.w >> rhs.a >> rhs.b;
}
friend ostream& operator << (ostream& os, info rhs){
return os << "(" << rhs.w << ", " << rhs.a << ", " << rhs.b << ")";
}
} item[N];
struct Edge{
int u, v, w;
Edge() {}
Edge(int u, int v, int w): u(u), v(v), w(w) {}
friend ostream& operator << (ostream &os, Edge &rhs){
return os << "(" << rhs.u << ", " << rhs.v << ", " << rhs.w << ")";
}
} edge[N];
struct SegTree{
int st[N << 2];
void build(int tl, int tr, int i){
st[i] = INF;
if(tl == tr) return;
int tm = tl + tr >> 1;
build(tl, tm, i<<1);
build(tm + 1, tr, i<<1|1);
}
void upd(int pos, int val, int tl, int tr, int i){
if(tl == tr){
st[i] = val;
return;
}
int tm = tl + tr >> 1;
if(pos <= tm) upd(pos, val, tl, tm, i<<1);
else upd(pos, val, tm + 1, tr, i<<1|1);
st[i] = min(st[i<<1], st[i<<1|1]);
}
int get(int l, int r, int tl, int tr, int i){
if(r < tl || tr < l || l > r) return INF;
if(l <= tl && tr <= r) return st[i];
int tm = tl + tr >> 1;
return min(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
}
} it;
int fset(int i){ return i == pa[i] ? i : pa[i] = fset(pa[i]); }
void uset(int u, int v){
int pu = fset(u),
pv = fset(v);
if(pu == pv){
if(u == v - 1) return;
u += 1;
if((R[pu] - L[pu] + 1) % 2) res -= min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
it.upd(u, item[u].a - item[u].b, 1, n, 1);
if((R[pu] - L[pu] + 1) % 2) res += min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
return;
}
if(sz[pu] % 2) res -= min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
if(sz[pv] % 2) res -= min(odd_min[pv], it.get(L[pv], R[pv], 1, n, 1));
if(sz[pu] % 2){
odd_min[pu] = min(odd_min[pu], even_min[pv]);
even_min[pu] = min(even_min[pu], odd_min[pv]);
}else{
odd_min[pu] = min(odd_min[pu], odd_min[pv]);
even_min[pu] = min(even_min[pu], even_min[pv]);
}
R[pu] = R[pv];
sz[pu] += sz[pv];
if(sz[pu] % 2){
res += min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
}
pa[pv] = pu;
}
int _N, _Q;
vector<int> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
n = _N;
for(int i = 1; i <= n; i++){
item[i].a = A[i - 1];
item[i].b = B[i - 1];
item[i].w = W[i - 1];
}
q = _Q;
for(int i = 1; i <= q; i++){
que[i].first = E[i - 1];
que[i].second = i;
}
sort(que + 1, que + q + 1);
for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;
sort(item + 1, item + n + 1, [](info x, info y){
return x.w < y.w;
});
int ti = 0;
for(int i = 1; i < n; i++){
edge[++ti] = Edge(i, i + 1, item[i + 1].w - item[i].w);
if(i + 2 <= n) edge[++ti] = Edge(i, i + 2, item[i + 2].w - item[i].w);
}
for(int i = 1; i <= n; i++){
odd_min[i] = item[i].a - item[i].b;
even_min[i] = INF;
L[i] = i; R[i] = i;
res += item[i].a;
}
sort(edge + 1, edge + ti + 1, [](Edge x, Edge y){
return x.w < y.w;
});
// for(int i = 1; i <= n; i++) cout << item[i] << "\n"; cout << "\n";
// for(int i = 1; i <= ti; i++) cout << edge[i] << "\n"; cout << "\n";
it.build(1, n, 1);
for(int i = 1, j = 0; i <= q; i++){
while(j < ti && edge[j + 1].w <= que[i].first){
++j;
uset(edge[j].u, edge[j].v);
}
answer[que[i].second] = res;
}
vector<int> R;
for(int i = 1; i <= n; i++) R.push_back(answer[i]);
return R;
}
//int32_t main() {
// assert(1 == scanf("%d", &_N));
// std::vector<int> W(_N), A(_N), B(_N);
// for (int i = 0; i < _N; i++)
// assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
// assert(1 == scanf("%d", &_Q));
// std::vector<int> E(_Q);
// for (int j = 0; j < _Q; j++)
// assert(1 == scanf("%d", &E[j]));
// fclose(stdin);
//
// std::vector<long long> R = calculate_costs(W, A, B, E);
//
// int S = (int)R.size();
// for (int j = 0; j < S; j++)
// printf("%lld\n", R[j]);
// fclose(stdout);
//
// return 0;
//}