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 "nile.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int N_MAX = 1e5;
const int Q_MAX = 1e5;
const int64 myINF = 1e18;
int64 answer;
struct DSU {
int father;
int le, ri;
int64 min_d[2], min_jump[2];
int64 local_answer;
} infos[1 + N_MAX];
struct elem {
int64 w;
int64 s, p;
int64 diff;
}; vector<elem> input;
bool byW (elem first, elem second) {return first.w < second.w;}
int __find (int a) {
if (infos[a].father == a) return a;
return infos[a].father = __find (infos[a].father);
}
void __merge (int a, int b) {
int x = __find (a), y = __find (b);
infos[y].father = x;
if (b == a + 1) {
answer -= infos[x].local_answer;
answer -= infos[y].local_answer;
infos[x].ri = infos[y].ri;
for (int t = 0; t < 2; t ++) {
infos[x].min_d[t] = min (infos[x].min_d[t], infos[y].min_d[t]);
infos[x].min_jump[t] = min (infos[x].min_jump[t], infos[y].min_jump[t]);
}
}
else {
answer -= infos[x].local_answer;
infos[x].min_jump[(a + 1) % 2] = min (infos[x].min_jump[(a + 1) % 2], input[a + 1].diff);
}
int l = infos[x].le, r = infos[x].ri;
if ((r - l + 1) % 2 == 0)
infos[x].local_answer = 0;
else
infos[x].local_answer = min (infos[x].min_d[l % 2], infos[x].min_jump[1 - l % 2]);
answer += infos[x].local_answer;
}
struct defEdge {
int a, b;
int64 cost;
};
bool compare_edges (defEdge e1, defEdge e2) {
if (e1.cost == e2.cost) return (e1.b == e1.a + 1);
return e1.cost < e2.cost;
}
vector<int64> calculate_costs (vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size ();
int Q = E.size ();
input.resize (N);
for (int i = 0; i < N; i ++) input[i] = {W[i], A[i], B[i], A[i] - B[i]};
int64 sumB = 0;
for (int i = 0; i < N; i ++) {
answer += input[i].diff;
sumB += input[i].p;
}
vector<pair<int, int>> querys (Q);
vector<int64> R(Q, 0);
for (int i = 0; i < Q; i ++) querys[i] = make_pair (E[i], i);
sort (input.begin (), input.end (), byW);
vector<defEdge> edges;
for (int i = 0; i < N; i ++) {
if (i < N - 1) edges.push_back ({i, i + 1, input[i + 1].w - input[i].w});
if (i < N - 2) edges.push_back ({i, i + 2, input[i + 2].w - input[i].w});
}
sort (edges.begin (), edges.end (), compare_edges);
for (int i = 0; i < N; i ++) {
infos[i].father = i;
infos[i].le = i, infos[i].ri = i;
infos[i].min_d[i % 2] = input[i].diff;
infos[i].min_jump[i % 2] = myINF;
infos[i].min_d[1 - i % 2] = infos[i].min_jump[1 - i % 2] = myINF;
infos[i].local_answer = input[i].diff;
}
sort (querys.begin (), querys.end ());
int e = 0;
for (int i = 0; i < Q; i ++) {
while (e < (int)edges.size () && edges[e].cost <= querys[i].first) {
__merge (edges[e].a, edges[e].b);
cout << edges[e].a << " " << edges[e].b << endl;
e ++;
}
R[querys[i].second] = sumB + answer;
}
return R;
}
/**int main () {
vector<int64> R = calculate_costs({1, 1, 1, 1, 1}, {5, 6, 4, 5, 3}, {0, 0, 0, 0, 0}, {5});
for (int r : R) cout << r << " ";
}**/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |