| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1109895 | Trisanu_Das | 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;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 1e5 + 5;
int max_val[MAXN] = {0};
int size[MAXN] = {0};
int parent[MAXN] = {0};
int value[MAXN][2] = {0};
int find(int r) {
return parent[r] == r ? r : parent[r] = find(parent[r]);
}
int calculate(int u) {
if (size[u] % 2 == 0) return 0;
return max(value[u][u & 1], max_val[u]);
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size();
int m = E.size();
vector<pair<int, pii>> v;
for (int i = 0; i < n; i++) {
v.push_back({W[i], {A[i], B[i]}});
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
W[i] = v[i].first;
A[i] = v[i].second.first;
B[i] = v[i].second.second;
}
vector<pii> q1, q2;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
value[i][i & 1] = B[i] - A[i];
max_val[i] = -2e9;
value[i][(i + 1) & 1] = -2e9;
}
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());
ll result_sum = 0;
for (int i = 0; i < n; i++) {
result_sum += A[i];
}
vector<pii> queries;
for (int i = 0; i < m; i++) {
queries.push_back({E[i], i});
}
sort(queries.begin(), queries.end());
int id1 = 0, id2 = 0;
vector<ll> res(m, 0);
for (auto [d, i] : queries) {
while (id1 < q1.size() && q1[id1].first <= d) {
int u = find(q1[id1].second), v = find(q1[id1].second + 1);
result_sum += calculate(u) + calculate(v);
parent[u] = v;
size[v] += size[u];
value[v][0] = max(value[v][0], value[u][0]);
value[v][1] = max(value[v][1], value[u][1]);
max_val[v] = max(max_val[v], max_val[u]);
result_sum -= calculate(v);
id1++;
}
while (id2 < q2.size() && q2[id2].first <= d) {
int u = find(q2[id2].second);
result_sum += calculate(u);
max_val[u] = max(max_val[u], B[q2[id2].second] - A[q2[id2].second]);
result_sum -= calculate(u);
id2++;
}
res[i] = result_sum;
}
return res;
}