#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
struct Nyan {
int ssm, sbg;
multiset<int> sm, bg;
int last_qry;
void init() {
ssm = sbg = 0;
sm.clear();
bg.clear();
last_qry = 0;
}
void insert(int x) {
if(x <= last_qry) {
sm.insert(x);
ssm += x;
} else {
bg.insert(x);
sbg += x;
}
}
void erase(int x) {
if(x <= last_qry) {
sm.erase(sm.find(x));
ssm -= x;
} else {
bg.erase(bg.find(x));
sbg -= x;
}
}
int eval(int x) {
while(sz(bg) && (*bg.begin()) <= x) {
int k = *bg.begin();
ssm += k;
sbg -= k;
sm.insert(k);
bg.erase(bg.begin());
}
last_qry = x;
return x * (sz(sm) - sz(bg)) - ssm + sbg;
}
} owo;
const int MAXN = 510;
const int MAXM = 100010;
struct Edge {
int a, b, ab, w;
};
struct Tree {
int n;
vector<Edge> te; // tree edge
vector<int> adj[MAXN];
int cc[MAXN]; // connected component
int d[MAXN]; // depth
int p[MAXN]; // parent
void init(int _n) {
n = _n;
te.clear();
rebuild();
}
void dfs(int v, int par, int dep, int cid) {
cc[v] = cid;
d[v] = dep;
for(auto &eid:adj[v]) {
int i = te[eid].ab ^ v;
if(i != par) {
p[i] = eid;
dfs(i, v, dep + 1, cid);
}
}
}
void rebuild() {
For(i, 1, n) {
adj[i].clear();
cc[i] = -1;
}
For(i, 0, sz(te) - 1) {
adj[te[i].a].eb(i);
adj[te[i].b].eb(i);
}
int num_cc = 0;
For(i, 1, n) if(cc[i] < 0) {
num_cc++;
dfs(i, i, 1, num_cc);
}
}
int climb(int a, int b) {
pii res(1e18, -1); // min weight, eid
auto up = [&](int k) {
auto &e = te[p[k]];
res = min(res, pii(e.w, p[k]));
return e.ab ^ k;
};
if(d[a] < d[b]) swap(a, b);
while(d[a] > d[b]) a = up(a);
while(a != b) {
a = up(a); b = up(b);
}
return res.S;
}
int add_edge(Edge e) {
if(cc[e.a] != cc[e.b]) {
te.eb(e);
rebuild();
return -1;
}
int eid = climb(e.a, e.b);
int res = te[eid].w;
te[eid] = e;
rebuild();
return res;
}
void out() {
For(i, 1, n) cout << cc[i] << " \n"[i == n];
for(auto &e:te) cout << e.a << "-" << e.b << " ";
cout << "\n";
}
} tr;
Edge ed[MAXM];
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// =^-w-^=
int n, m; cin >> n >> m;
For(i, 1, m) {
auto &e = ed[i];
cin >> e.a >> e.b >> e.w;
e.ab = e.a ^ e.b;
}
sort(ed + 1, ed + m + 1, [&](auto &a, auto &b) {
return a.w < b.w;
});
owo.init();
tr.init(n);
// tr.out();
vector<pair<int, pii>> ev; // {time, {old, new}}
For(i, 1, m) {
auto res = tr.add_edge(ed[i]);
if(res < 0) owo.insert(ed[i].w);
else {
int a = res;
int b = ed[i].w;
int mi = b - ((b - a) / 2);
ev.eb(mi, pii(a, b));
// cout << mi << " " << a << " " << b << "\n";
}
// tr.out();
}
sort(all(ev));
reverse(all(ev));
int q; cin >> q;
while(q--) {
int x; cin >> x;
while(sz(ev) && ev.back().F <= x) {
auto p = ev.back().S;
owo.erase(p.F);
owo.insert(p.S);
ev.pop_back();
}
cout << owo.eval(x) << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1822 ms |
6864 KB |
Output is correct |
21 |
Correct |
1590 ms |
6804 KB |
Output is correct |
22 |
Correct |
1738 ms |
6660 KB |
Output is correct |
23 |
Correct |
1711 ms |
6764 KB |
Output is correct |
24 |
Correct |
1761 ms |
6700 KB |
Output is correct |
25 |
Correct |
1777 ms |
6756 KB |
Output is correct |
26 |
Correct |
1783 ms |
6780 KB |
Output is correct |
27 |
Correct |
1803 ms |
6812 KB |
Output is correct |
28 |
Correct |
1831 ms |
6728 KB |
Output is correct |
29 |
Correct |
1832 ms |
6660 KB |
Output is correct |
30 |
Correct |
1844 ms |
6888 KB |
Output is correct |
31 |
Correct |
1852 ms |
6744 KB |
Output is correct |
32 |
Correct |
1825 ms |
6736 KB |
Output is correct |
33 |
Correct |
1913 ms |
6780 KB |
Output is correct |
34 |
Correct |
2025 ms |
6740 KB |
Output is correct |
35 |
Correct |
1918 ms |
6652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1911 ms |
24712 KB |
Output is correct |
5 |
Correct |
2040 ms |
28384 KB |
Output is correct |
6 |
Correct |
1944 ms |
28404 KB |
Output is correct |
7 |
Correct |
1285 ms |
30268 KB |
Output is correct |
8 |
Correct |
1174 ms |
30296 KB |
Output is correct |
9 |
Correct |
1142 ms |
30324 KB |
Output is correct |
10 |
Correct |
1853 ms |
28452 KB |
Output is correct |
11 |
Correct |
1150 ms |
30408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
209 ms |
12796 KB |
Output is correct |
21 |
Correct |
206 ms |
22508 KB |
Output is correct |
22 |
Correct |
191 ms |
22408 KB |
Output is correct |
23 |
Correct |
182 ms |
22440 KB |
Output is correct |
24 |
Correct |
179 ms |
22348 KB |
Output is correct |
25 |
Correct |
180 ms |
22404 KB |
Output is correct |
26 |
Correct |
196 ms |
22364 KB |
Output is correct |
27 |
Correct |
185 ms |
22388 KB |
Output is correct |
28 |
Correct |
190 ms |
22316 KB |
Output is correct |
29 |
Correct |
189 ms |
22376 KB |
Output is correct |
30 |
Correct |
197 ms |
22444 KB |
Output is correct |
31 |
Correct |
178 ms |
22232 KB |
Output is correct |
32 |
Correct |
208 ms |
22940 KB |
Output is correct |
33 |
Correct |
182 ms |
22240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1822 ms |
6864 KB |
Output is correct |
21 |
Correct |
1590 ms |
6804 KB |
Output is correct |
22 |
Correct |
1738 ms |
6660 KB |
Output is correct |
23 |
Correct |
1711 ms |
6764 KB |
Output is correct |
24 |
Correct |
1761 ms |
6700 KB |
Output is correct |
25 |
Correct |
1777 ms |
6756 KB |
Output is correct |
26 |
Correct |
1783 ms |
6780 KB |
Output is correct |
27 |
Correct |
1803 ms |
6812 KB |
Output is correct |
28 |
Correct |
1831 ms |
6728 KB |
Output is correct |
29 |
Correct |
1832 ms |
6660 KB |
Output is correct |
30 |
Correct |
1844 ms |
6888 KB |
Output is correct |
31 |
Correct |
1852 ms |
6744 KB |
Output is correct |
32 |
Correct |
1825 ms |
6736 KB |
Output is correct |
33 |
Correct |
1913 ms |
6780 KB |
Output is correct |
34 |
Correct |
2025 ms |
6740 KB |
Output is correct |
35 |
Correct |
1918 ms |
6652 KB |
Output is correct |
36 |
Correct |
1799 ms |
6928 KB |
Output is correct |
37 |
Correct |
1607 ms |
8896 KB |
Output is correct |
38 |
Correct |
1653 ms |
8820 KB |
Output is correct |
39 |
Correct |
1727 ms |
8548 KB |
Output is correct |
40 |
Correct |
1730 ms |
8820 KB |
Output is correct |
41 |
Correct |
1766 ms |
8692 KB |
Output is correct |
42 |
Correct |
1843 ms |
8688 KB |
Output is correct |
43 |
Correct |
1816 ms |
8632 KB |
Output is correct |
44 |
Correct |
1776 ms |
8680 KB |
Output is correct |
45 |
Correct |
1909 ms |
8864 KB |
Output is correct |
46 |
Correct |
1824 ms |
8680 KB |
Output is correct |
47 |
Correct |
1803 ms |
8732 KB |
Output is correct |
48 |
Correct |
1761 ms |
8656 KB |
Output is correct |
49 |
Correct |
1773 ms |
8612 KB |
Output is correct |
50 |
Correct |
1923 ms |
8880 KB |
Output is correct |
51 |
Correct |
1770 ms |
8692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1822 ms |
6864 KB |
Output is correct |
21 |
Correct |
1590 ms |
6804 KB |
Output is correct |
22 |
Correct |
1738 ms |
6660 KB |
Output is correct |
23 |
Correct |
1711 ms |
6764 KB |
Output is correct |
24 |
Correct |
1761 ms |
6700 KB |
Output is correct |
25 |
Correct |
1777 ms |
6756 KB |
Output is correct |
26 |
Correct |
1783 ms |
6780 KB |
Output is correct |
27 |
Correct |
1803 ms |
6812 KB |
Output is correct |
28 |
Correct |
1831 ms |
6728 KB |
Output is correct |
29 |
Correct |
1832 ms |
6660 KB |
Output is correct |
30 |
Correct |
1844 ms |
6888 KB |
Output is correct |
31 |
Correct |
1852 ms |
6744 KB |
Output is correct |
32 |
Correct |
1825 ms |
6736 KB |
Output is correct |
33 |
Correct |
1913 ms |
6780 KB |
Output is correct |
34 |
Correct |
2025 ms |
6740 KB |
Output is correct |
35 |
Correct |
1918 ms |
6652 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
0 ms |
340 KB |
Output is correct |
39 |
Correct |
1911 ms |
24712 KB |
Output is correct |
40 |
Correct |
2040 ms |
28384 KB |
Output is correct |
41 |
Correct |
1944 ms |
28404 KB |
Output is correct |
42 |
Correct |
1285 ms |
30268 KB |
Output is correct |
43 |
Correct |
1174 ms |
30296 KB |
Output is correct |
44 |
Correct |
1142 ms |
30324 KB |
Output is correct |
45 |
Correct |
1853 ms |
28452 KB |
Output is correct |
46 |
Correct |
1150 ms |
30408 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
209 ms |
12796 KB |
Output is correct |
49 |
Correct |
206 ms |
22508 KB |
Output is correct |
50 |
Correct |
191 ms |
22408 KB |
Output is correct |
51 |
Correct |
182 ms |
22440 KB |
Output is correct |
52 |
Correct |
179 ms |
22348 KB |
Output is correct |
53 |
Correct |
180 ms |
22404 KB |
Output is correct |
54 |
Correct |
196 ms |
22364 KB |
Output is correct |
55 |
Correct |
185 ms |
22388 KB |
Output is correct |
56 |
Correct |
190 ms |
22316 KB |
Output is correct |
57 |
Correct |
189 ms |
22376 KB |
Output is correct |
58 |
Correct |
197 ms |
22444 KB |
Output is correct |
59 |
Correct |
178 ms |
22232 KB |
Output is correct |
60 |
Correct |
208 ms |
22940 KB |
Output is correct |
61 |
Correct |
182 ms |
22240 KB |
Output is correct |
62 |
Correct |
1799 ms |
6928 KB |
Output is correct |
63 |
Correct |
1607 ms |
8896 KB |
Output is correct |
64 |
Correct |
1653 ms |
8820 KB |
Output is correct |
65 |
Correct |
1727 ms |
8548 KB |
Output is correct |
66 |
Correct |
1730 ms |
8820 KB |
Output is correct |
67 |
Correct |
1766 ms |
8692 KB |
Output is correct |
68 |
Correct |
1843 ms |
8688 KB |
Output is correct |
69 |
Correct |
1816 ms |
8632 KB |
Output is correct |
70 |
Correct |
1776 ms |
8680 KB |
Output is correct |
71 |
Correct |
1909 ms |
8864 KB |
Output is correct |
72 |
Correct |
1824 ms |
8680 KB |
Output is correct |
73 |
Correct |
1803 ms |
8732 KB |
Output is correct |
74 |
Correct |
1761 ms |
8656 KB |
Output is correct |
75 |
Correct |
1773 ms |
8612 KB |
Output is correct |
76 |
Correct |
1923 ms |
8880 KB |
Output is correct |
77 |
Correct |
1770 ms |
8692 KB |
Output is correct |
78 |
Correct |
1940 ms |
27436 KB |
Output is correct |
79 |
Correct |
1721 ms |
29612 KB |
Output is correct |
80 |
Correct |
1817 ms |
28648 KB |
Output is correct |
81 |
Correct |
1886 ms |
28612 KB |
Output is correct |
82 |
Correct |
1904 ms |
27560 KB |
Output is correct |
83 |
Correct |
1927 ms |
27716 KB |
Output is correct |
84 |
Correct |
2015 ms |
27480 KB |
Output is correct |
85 |
Correct |
2028 ms |
27504 KB |
Output is correct |
86 |
Correct |
1921 ms |
27468 KB |
Output is correct |
87 |
Correct |
2021 ms |
29172 KB |
Output is correct |
88 |
Correct |
1961 ms |
27468 KB |
Output is correct |
89 |
Correct |
1991 ms |
27468 KB |
Output is correct |
90 |
Correct |
1927 ms |
27708 KB |
Output is correct |
91 |
Correct |
1923 ms |
27404 KB |
Output is correct |
92 |
Correct |
2069 ms |
30360 KB |
Output is correct |
93 |
Correct |
2116 ms |
28544 KB |
Output is correct |