| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1109895 | Trisanu_Das | 나일강 (IOI24_nile) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}