# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
1038702 |
2024-07-30T06:32:55 Z |
정민찬(#10987) |
JOI tour (JOI24_joitour) |
C++17 |
|
2331 ms |
122584 KB |
#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll B = 400;
struct Fenwick {
vector<ll> tree;
void init(ll n) {
tree.resize(n+1);
}
void update(ll i, ll v, ll n) {
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
ll qry(ll i) {
ll ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
ll qry(ll l, ll r) {
return qry(r) - qry(l-1);
}
};
struct LazySegmentTree{
vector<ll> tree;
vector<ll> tree2;
vector<ll> cnt;
vector<ll> lazy;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.assign(sz, 0);
tree2.assign(sz, 0);
cnt.assign(sz, 0);
lazy.assign(sz, 0);
}
void propagate(ll node, ll s, ll e) {
tree[node] += lazy[node] * cnt[node];
tree2[node] += lazy[node] * (e-s+1);
if (s != e) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
void update(ll node, ll s, ll e, ll l, ll r, ll v) {
propagate(node, s, e);
if (l > e || s > r) return;
if (l <= s && e <= r) {
lazy[node] = v;
propagate(node, s, e);
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, l, r, v);
update(node*2+1, mid+1, e, l, r, v);
tree[node] = tree[node*2] + tree[node*2+1];
cnt[node] = cnt[node*2] + cnt[node*2+1];
}
void modify(ll node, ll s, ll e, ll tar, ll state) {
propagate(node, s, e);
if (s > tar || tar > e) return;
if (s == e) {
cnt[node] = state;
if (state == 1) tree[node] = tree2[node];
else tree[node] = 0;
return;
}
ll mid = s + e >> 1;
modify(node*2, s, mid, tar, state);
modify(node*2+1, mid+1, e, tar, state);
tree[node] = tree[node*2] + tree[node*2+1];
cnt[node] = cnt[node*2] + cnt[node*2+1];
}
ll query(ll node, ll s, ll e, ll l, ll r) {
propagate(node, s, e);
if (l > e || s > r) return 0;
if (l <= s && e <= r) return tree[node];
ll mid = s + e >> 1;
return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
}
};
ll n;
vector<ll> adj[200010];
vector<ll> g[200010];
ll T[3];
ll in[200010], out[200010];
ll pv;
ll sz[200010], par[200010];
ll dep[200010];
void dfs(ll x, ll p) {
sz[x] = 1;
for (auto &y : adj[x]) {
if (y == p) continue;
g[x].push_back(y);
dep[y] = dep[x] + 1;
par[y] = x;
dfs(y, x);
sz[x] += sz[y];
if (sz[g[x][0]] < sz[y]) {
swap(g[x][0], g[x].back());
}
}
}
ll tp[200010];
void dfs2(ll x) {
in[x] = ++ pv;
for (auto &y : g[x]) {
tp[y] = y == g[x][0] ? tp[x] : y;
dfs2(y);
}
out[x] = pv;
}
Fenwick seg0, seg1, seg2;
LazySegmentTree sub0, sub2;
LazySegmentTree psub0, psub2;
//LazySegmentTree sub20, sub02;
ll ans = 0;
ll F[200010];
ll TS[3];
vector<ll> lot;
ll sum[200010];
void init(int _N, vector<int> _F, vector<int> U, vector<int> V, int Q) {
n = _N;
for (ll i=1; i<=n; i++) {
F[i] = _F[i-1];
}
for (ll i=1; i<=n; i++) {
T[F[i]] ++;
}
for (ll i=0; i<n-1; i++) {
adj[U[i]+1].push_back(V[i] + 1);
adj[V[i]+1].push_back(U[i] + 1);
}
dep[1] = 1;
dfs(1, 0);
tp[1] = 1;
dfs2(1);
seg0.init(n); seg1.init(n); seg2.init(n);
sub0.init(n); sub2.init(n);
psub0.init(n); psub2.init(n);
//sub02.init(n); sub20.init(n);
for (ll i=1; i<=n; i++) {
if (F[i] == 0) {
seg0.update(in[i], 1, n);
}
else if (F[i] == 2) {
seg2.update(in[i], 1, n);
}
else {
seg1.update(in[i], 1, n);
}
}
for (ll i=1; i<=n; i++) {
ll ret0 = seg0.qry(in[i], out[i]);
ll ret2 = seg2.qry(in[i], out[i]);
if (F[i] == 1) {
sub0.modify(1, 1, n, in[i], 1);
sub2.modify(1, 1, n, in[i], 1);
ans += (T[0] - ret0) * (T[2] - ret2);
TS[0] += ret0;
TS[2] += ret2;
}
if (i != 1 && F[par[i]] == 1) {
psub0.modify(1, 1, n, in[i], 1);
psub2.modify(1, 1, n, in[i], 1);
ans += ret0 * ret2;
}
sub0.update(1, 1, n, in[i], in[i], ret0);
sub2.update(1, 1, n, in[i], in[i], ret2);
//sub02.update(1, 1, n, in[i], in[i], ret2);
//sub20.update(1, 1, n, in[i], in[i], ret0);
psub0.update(1, 1, n, in[i], in[i], ret0);
psub2.update(1, 1, n, in[i], in[i], ret2);
}
for (ll i=1; i<=n; i++) {
if (g[i].size() > B) {
for (auto &j : g[i]) {
sum[i] += seg0.qry(in[j], out[j]) * seg2.qry(in[j], out[j]);
}
lot.push_back(i);
}
}
}
ll Qquery1(ll x, ll t) {
ll ret = 0;
while (x) {
if (t == 0)
ret += sub0.query(1, 1, n, in[tp[x]], in[x]);
else
ret += sub2.query(1, 1, n, in[tp[x]], in[x]);
x = par[tp[x]];
}
return ret;
}
ll Qquery2(ll x, ll t) {
ll ret = 0;
while (x) {
if (tp[x] != 1 && F[par[tp[x]]] == 1) {
if (t == 0)
psub0.modify(1, 1, n, in[tp[x]], 1);
else
psub2.modify(1, 1, n, in[tp[x]], 1);
}
else {
if (t == 0)
psub0.modify(1, 1, n, in[tp[x]], 0);
else
psub2.modify(1, 1, n, in[tp[x]], 0);
}
if (t == 0)
ret += psub0.query(1, 1, n, in[tp[x]], in[x]);
else
ret += psub2.query(1, 1, n, in[tp[x]], in[x]);
x = par[tp[x]];
}
return ret;
}
ll Qquery3(ll x) {
ll ret = 0;
while (x) {
ret += seg1.qry(in[tp[x]], in[x]);
x = par[tp[x]];
}
return ret;
}
void Uupdate0(ll x, ll v) {
while (x) {
sub0.update(1, 1, n, in[tp[x]], in[x], v);
psub0.update(1, 1, n, in[tp[x]], in[x], v);
x = par[tp[x]];
}
}
void Uupdate2(ll x, ll v) {
while (x) {
sub2.update(1, 1, n, in[tp[x]], in[x], v);
psub2.update(1, 1, n, in[tp[x]], in[x], v);
x = par[tp[x]];
}
}
void change(int X, int v) {
X ++;
if (F[X] == 1) {
if (g[X].size() > B) ans -= sum[X];
else {
for (auto &y : g[X]) {
ans -= seg0.qry(in[y], out[y]) * seg2.qry(in[y], out[y]);
}
}
ans -= (T[0] - seg0.qry(in[X], out[X])) * (T[2] - seg2.qry(in[X], out[X]));
if (!g[X].empty()) {
psub0.modify(1, 1, n, in[g[X][0]], 0);
psub2.modify(1, 1, n, in[g[X][0]], 0);
}
sub0.modify(1, 1, n, in[X], 0);
sub2.modify(1, 1, n, in[X], 0);
T[1] --;
seg1.update(in[X], -1, n);
TS[0] -= seg0.qry(in[X], out[X]);
TS[2] -= seg2.qry(in[X], out[X]);
}
else if (F[X] == 2) {
Uupdate2(X, -1);
TS[2] -= Qquery3(X);
T[2] --;
ans += TS[0] - Qquery1(X, 0);
ans -= T[0] * (T[1] - Qquery3(X));
ans -= Qquery2(X, 0);
for (auto &y : lot) {
if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
return in[uu] < in[vv];
}) - g[y].begin() - 1;
ll ch = g[y][idx];
sum[y] -= seg0.qry(in[ch], out[ch]);
}
}
seg2.update(in[X], -1, n);
}
else if (F[X] == 0) {
Uupdate0(X, -1);
TS[0] -= Qquery3(X);
T[0] --;
ans += TS[2] - Qquery1(X, 2);
ans -= T[2] * (T[1] - Qquery3(X));
ans -= Qquery2(X, 2);
for (auto &y : lot) {
if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
return in[uu] < in[vv];
}) - g[y].begin() - 1;
ll ch = g[y][idx];
sum[y] -= seg2.qry(in[ch], out[ch]);
}
}
seg0.update(in[X], -1, n);
}
F[X] = v;
if (F[X] == 1) {
if (g[X].size() > B) ans += sum[X];
else {
for (auto &y : g[X]) {
ans += seg0.qry(in[y], out[y]) * seg2.qry(in[y], out[y]);
}
}
ans += (T[0] - seg0.qry(in[X], out[X])) * (T[2] - seg2.qry(in[X], out[X]));
if (!g[X].empty()) {
psub0.modify(1, 1, n, in[g[X][0]], 1);
psub2.modify(1, 1, n, in[g[X][0]], 1);
}
sub0.modify(1, 1, n, in[X], 1);
sub2.modify(1, 1, n, in[X], 1);
T[1] ++;
seg1.update(in[X], 1, n);
TS[0] += seg0.qry(in[X], out[X]);
TS[2] += seg2.qry(in[X], out[X]);
}
else if (F[X] == 2) {
Uupdate2(X, 1);
TS[2] += Qquery3(X);
T[2] ++;
ans -= TS[0] - Qquery1(X, 0);
ans += T[0] * (T[1] - Qquery3(X));
ans += Qquery2(X, 0);
for (auto &y : lot) {
if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
return in[uu] < in[vv];
}) - g[y].begin() - 1;
ll ch = g[y][idx];
sum[y] += seg0.qry(in[ch], out[ch]);
}
}
seg2.update(in[X], 1, n);
}
else if (F[X] == 0) {
Uupdate0(X, 1);
TS[0] += Qquery3(X);
T[0] ++;
ans -= TS[2] - Qquery1(X, 2);
ans += T[2] * (T[1] - Qquery3(X));
ans += Qquery2(X, 2);
for (auto &y : lot) {
if (y != X && in[y] <= in[X] && in[X] <= out[y]) {
ll idx = upper_bound(g[y].begin(), g[y].end(), X, [&] (ll uu, ll vv) {
return in[uu] < in[vv];
}) - g[y].begin() - 1;
ll ch = g[y][idx];
sum[y] += seg2.qry(in[ch], out[ch]);
}
}
seg0.update(in[X], 1, n);
}
}
long long num_tours() {
return T[0] * T[1] * T[2] - ans;
}
/*
int main() {
int N;
assert(scanf("%d", &N) == 1);
std::vector<int> _F(N);
for (int i = 0; i < N; i++) {
assert(scanf("%d", &_F[i]) == 1);
}
std::vector<int> U(N - 1), V(N - 1);
for (int j = 0; j < N - 1; j++) {
assert(scanf("%d %d", &U[j], &V[j]) == 2);
}
int Q;
assert(scanf("%d", &Q) == 1);
init(N, _F, U, V, Q);
printf("%lld\n", num_tours());
fflush(stdout);
for (int k = 0; k < Q; k++) {
int X, Y;
assert(scanf("%d %d", &X, &Y) == 2);
change(X, Y);
printf("%lld\n", num_tours());
fflush(stdout);
}
}
*/
Compilation message
joitour.cpp: In member function 'void LazySegmentTree::init(ll)':
joitour.cpp:41:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
41 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
joitour.cpp: In member function 'void LazySegmentTree::update(ll, ll, ll, ll, ll, ll)':
joitour.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | ll mid = s + e >> 1;
| ~~^~~
joitour.cpp: In member function 'void LazySegmentTree::modify(ll, ll, ll, ll, ll)':
joitour.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | ll mid = s + e >> 1;
| ~~^~~
joitour.cpp: In member function 'll LazySegmentTree::query(ll, ll, ll, ll, ll)':
joitour.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | ll mid = s + e >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
15960 KB |
Output is correct |
2 |
Correct |
2 ms |
15960 KB |
Output is correct |
3 |
Correct |
2 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
16216 KB |
Output is correct |
5 |
Correct |
3 ms |
15960 KB |
Output is correct |
6 |
Correct |
3 ms |
15960 KB |
Output is correct |
7 |
Correct |
3 ms |
15960 KB |
Output is correct |
8 |
Correct |
3 ms |
15960 KB |
Output is correct |
9 |
Correct |
4 ms |
16216 KB |
Output is correct |
10 |
Correct |
3 ms |
16216 KB |
Output is correct |
11 |
Correct |
2 ms |
15960 KB |
Output is correct |
12 |
Correct |
2 ms |
15960 KB |
Output is correct |
13 |
Correct |
2 ms |
15960 KB |
Output is correct |
14 |
Correct |
2 ms |
15960 KB |
Output is correct |
15 |
Correct |
4 ms |
15960 KB |
Output is correct |
16 |
Correct |
4 ms |
16020 KB |
Output is correct |
17 |
Correct |
3 ms |
15960 KB |
Output is correct |
18 |
Correct |
3 ms |
15960 KB |
Output is correct |
19 |
Correct |
4 ms |
16268 KB |
Output is correct |
20 |
Correct |
4 ms |
11864 KB |
Output is correct |
21 |
Correct |
3 ms |
11864 KB |
Output is correct |
22 |
Correct |
3 ms |
11864 KB |
Output is correct |
23 |
Correct |
3 ms |
11864 KB |
Output is correct |
24 |
Correct |
4 ms |
12120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
15960 KB |
Output is correct |
2 |
Correct |
2 ms |
15960 KB |
Output is correct |
3 |
Correct |
2 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
16216 KB |
Output is correct |
5 |
Correct |
3 ms |
15960 KB |
Output is correct |
6 |
Correct |
3 ms |
15960 KB |
Output is correct |
7 |
Correct |
3 ms |
15960 KB |
Output is correct |
8 |
Correct |
3 ms |
15960 KB |
Output is correct |
9 |
Correct |
4 ms |
16216 KB |
Output is correct |
10 |
Correct |
3 ms |
16216 KB |
Output is correct |
11 |
Correct |
2 ms |
15960 KB |
Output is correct |
12 |
Correct |
2 ms |
15960 KB |
Output is correct |
13 |
Correct |
2 ms |
15960 KB |
Output is correct |
14 |
Correct |
2 ms |
15960 KB |
Output is correct |
15 |
Correct |
4 ms |
15960 KB |
Output is correct |
16 |
Correct |
4 ms |
16020 KB |
Output is correct |
17 |
Correct |
3 ms |
15960 KB |
Output is correct |
18 |
Correct |
3 ms |
15960 KB |
Output is correct |
19 |
Correct |
4 ms |
16268 KB |
Output is correct |
20 |
Correct |
4 ms |
11864 KB |
Output is correct |
21 |
Correct |
3 ms |
11864 KB |
Output is correct |
22 |
Correct |
3 ms |
11864 KB |
Output is correct |
23 |
Correct |
3 ms |
11864 KB |
Output is correct |
24 |
Correct |
4 ms |
12120 KB |
Output is correct |
25 |
Correct |
15 ms |
13912 KB |
Output is correct |
26 |
Correct |
18 ms |
13400 KB |
Output is correct |
27 |
Correct |
18 ms |
13400 KB |
Output is correct |
28 |
Correct |
24 ms |
13656 KB |
Output is correct |
29 |
Correct |
23 ms |
13400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
15960 KB |
Output is correct |
2 |
Correct |
739 ms |
117196 KB |
Output is correct |
3 |
Correct |
907 ms |
115408 KB |
Output is correct |
4 |
Correct |
685 ms |
113320 KB |
Output is correct |
5 |
Correct |
820 ms |
116136 KB |
Output is correct |
6 |
Correct |
482 ms |
107020 KB |
Output is correct |
7 |
Correct |
483 ms |
106836 KB |
Output is correct |
8 |
Correct |
740 ms |
106576 KB |
Output is correct |
9 |
Correct |
724 ms |
106864 KB |
Output is correct |
10 |
Correct |
711 ms |
106996 KB |
Output is correct |
11 |
Correct |
663 ms |
107336 KB |
Output is correct |
12 |
Correct |
672 ms |
110644 KB |
Output is correct |
13 |
Correct |
769 ms |
110548 KB |
Output is correct |
14 |
Correct |
584 ms |
110500 KB |
Output is correct |
15 |
Correct |
765 ms |
109904 KB |
Output is correct |
16 |
Correct |
703 ms |
118432 KB |
Output is correct |
17 |
Correct |
2 ms |
11864 KB |
Output is correct |
18 |
Correct |
3 ms |
11864 KB |
Output is correct |
19 |
Correct |
2 ms |
11864 KB |
Output is correct |
20 |
Correct |
2 ms |
11864 KB |
Output is correct |
21 |
Correct |
663 ms |
107216 KB |
Output is correct |
22 |
Correct |
699 ms |
107436 KB |
Output is correct |
23 |
Correct |
558 ms |
107344 KB |
Output is correct |
24 |
Correct |
698 ms |
107412 KB |
Output is correct |
25 |
Correct |
562 ms |
105448 KB |
Output is correct |
26 |
Correct |
575 ms |
105276 KB |
Output is correct |
27 |
Correct |
519 ms |
105376 KB |
Output is correct |
28 |
Correct |
722 ms |
105276 KB |
Output is correct |
29 |
Correct |
409 ms |
120964 KB |
Output is correct |
30 |
Correct |
415 ms |
120800 KB |
Output is correct |
31 |
Correct |
320 ms |
120900 KB |
Output is correct |
32 |
Correct |
420 ms |
120956 KB |
Output is correct |
33 |
Correct |
427 ms |
106700 KB |
Output is correct |
34 |
Correct |
449 ms |
106660 KB |
Output is correct |
35 |
Correct |
369 ms |
106720 KB |
Output is correct |
36 |
Correct |
500 ms |
106648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
13912 KB |
Output is correct |
2 |
Correct |
2 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
15960 KB |
Output is correct |
5 |
Correct |
3 ms |
16008 KB |
Output is correct |
6 |
Correct |
3 ms |
15960 KB |
Output is correct |
7 |
Correct |
4 ms |
16216 KB |
Output is correct |
8 |
Correct |
17 ms |
17868 KB |
Output is correct |
9 |
Correct |
382 ms |
122164 KB |
Output is correct |
10 |
Correct |
411 ms |
122192 KB |
Output is correct |
11 |
Correct |
351 ms |
122312 KB |
Output is correct |
12 |
Correct |
443 ms |
122364 KB |
Output is correct |
13 |
Correct |
448 ms |
69256 KB |
Output is correct |
14 |
Correct |
458 ms |
69188 KB |
Output is correct |
15 |
Correct |
442 ms |
69260 KB |
Output is correct |
16 |
Correct |
512 ms |
69200 KB |
Output is correct |
17 |
Correct |
451 ms |
69168 KB |
Output is correct |
18 |
Correct |
472 ms |
69200 KB |
Output is correct |
19 |
Correct |
922 ms |
122256 KB |
Output is correct |
20 |
Correct |
969 ms |
122448 KB |
Output is correct |
21 |
Correct |
965 ms |
122144 KB |
Output is correct |
22 |
Correct |
1031 ms |
122524 KB |
Output is correct |
23 |
Correct |
892 ms |
122172 KB |
Output is correct |
24 |
Correct |
975 ms |
122584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
15960 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
15960 KB |
Output is correct |
5 |
Correct |
3 ms |
16024 KB |
Output is correct |
6 |
Correct |
4 ms |
16216 KB |
Output is correct |
7 |
Correct |
19 ms |
17496 KB |
Output is correct |
8 |
Correct |
434 ms |
108204 KB |
Output is correct |
9 |
Correct |
445 ms |
108112 KB |
Output is correct |
10 |
Correct |
400 ms |
108280 KB |
Output is correct |
11 |
Correct |
455 ms |
108368 KB |
Output is correct |
12 |
Correct |
640 ms |
62032 KB |
Output is correct |
13 |
Correct |
904 ms |
62040 KB |
Output is correct |
14 |
Correct |
910 ms |
62216 KB |
Output is correct |
15 |
Correct |
845 ms |
62220 KB |
Output is correct |
16 |
Correct |
1035 ms |
62036 KB |
Output is correct |
17 |
Correct |
871 ms |
62288 KB |
Output is correct |
18 |
Correct |
1388 ms |
108112 KB |
Output is correct |
19 |
Correct |
2048 ms |
108112 KB |
Output is correct |
20 |
Correct |
1956 ms |
108112 KB |
Output is correct |
21 |
Correct |
1830 ms |
108256 KB |
Output is correct |
22 |
Correct |
2331 ms |
108288 KB |
Output is correct |
23 |
Correct |
1916 ms |
108112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
15960 KB |
Output is correct |
2 |
Correct |
2 ms |
15960 KB |
Output is correct |
3 |
Correct |
2 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
16216 KB |
Output is correct |
5 |
Correct |
3 ms |
15960 KB |
Output is correct |
6 |
Correct |
3 ms |
15960 KB |
Output is correct |
7 |
Correct |
3 ms |
15960 KB |
Output is correct |
8 |
Correct |
3 ms |
15960 KB |
Output is correct |
9 |
Correct |
4 ms |
16216 KB |
Output is correct |
10 |
Correct |
3 ms |
16216 KB |
Output is correct |
11 |
Correct |
2 ms |
15960 KB |
Output is correct |
12 |
Correct |
2 ms |
15960 KB |
Output is correct |
13 |
Correct |
2 ms |
15960 KB |
Output is correct |
14 |
Correct |
2 ms |
15960 KB |
Output is correct |
15 |
Correct |
4 ms |
15960 KB |
Output is correct |
16 |
Correct |
4 ms |
16020 KB |
Output is correct |
17 |
Correct |
3 ms |
15960 KB |
Output is correct |
18 |
Correct |
3 ms |
15960 KB |
Output is correct |
19 |
Correct |
4 ms |
16268 KB |
Output is correct |
20 |
Correct |
4 ms |
11864 KB |
Output is correct |
21 |
Correct |
3 ms |
11864 KB |
Output is correct |
22 |
Correct |
3 ms |
11864 KB |
Output is correct |
23 |
Correct |
3 ms |
11864 KB |
Output is correct |
24 |
Correct |
4 ms |
12120 KB |
Output is correct |
25 |
Correct |
15 ms |
13912 KB |
Output is correct |
26 |
Correct |
18 ms |
13400 KB |
Output is correct |
27 |
Correct |
18 ms |
13400 KB |
Output is correct |
28 |
Correct |
24 ms |
13656 KB |
Output is correct |
29 |
Correct |
23 ms |
13400 KB |
Output is correct |
30 |
Correct |
532 ms |
65104 KB |
Output is correct |
31 |
Correct |
631 ms |
66128 KB |
Output is correct |
32 |
Correct |
585 ms |
66128 KB |
Output is correct |
33 |
Correct |
617 ms |
66628 KB |
Output is correct |
34 |
Correct |
558 ms |
66896 KB |
Output is correct |
35 |
Correct |
613 ms |
65756 KB |
Output is correct |
36 |
Correct |
862 ms |
62296 KB |
Output is correct |
37 |
Correct |
870 ms |
62296 KB |
Output is correct |
38 |
Correct |
923 ms |
62096 KB |
Output is correct |
39 |
Correct |
894 ms |
62544 KB |
Output is correct |
40 |
Correct |
845 ms |
62288 KB |
Output is correct |
41 |
Correct |
776 ms |
62288 KB |
Output is correct |
42 |
Correct |
516 ms |
63824 KB |
Output is correct |
43 |
Correct |
688 ms |
63280 KB |
Output is correct |
44 |
Correct |
610 ms |
63568 KB |
Output is correct |
45 |
Correct |
610 ms |
63956 KB |
Output is correct |
46 |
Correct |
634 ms |
63312 KB |
Output is correct |
47 |
Correct |
609 ms |
64232 KB |
Output is correct |
48 |
Correct |
521 ms |
66628 KB |
Output is correct |
49 |
Correct |
538 ms |
67916 KB |
Output is correct |
50 |
Correct |
624 ms |
66292 KB |
Output is correct |
51 |
Correct |
556 ms |
62288 KB |
Output is correct |
52 |
Correct |
796 ms |
62276 KB |
Output is correct |
53 |
Correct |
694 ms |
62288 KB |
Output is correct |
54 |
Correct |
709 ms |
62288 KB |
Output is correct |
55 |
Correct |
710 ms |
62268 KB |
Output is correct |
56 |
Correct |
668 ms |
62288 KB |
Output is correct |
57 |
Correct |
571 ms |
61572 KB |
Output is correct |
58 |
Correct |
628 ms |
61572 KB |
Output is correct |
59 |
Correct |
586 ms |
61512 KB |
Output is correct |
60 |
Correct |
630 ms |
61568 KB |
Output is correct |
61 |
Correct |
545 ms |
61492 KB |
Output is correct |
62 |
Correct |
384 ms |
69196 KB |
Output is correct |
63 |
Correct |
428 ms |
69184 KB |
Output is correct |
64 |
Correct |
435 ms |
69200 KB |
Output is correct |
65 |
Correct |
417 ms |
69196 KB |
Output is correct |
66 |
Correct |
398 ms |
69452 KB |
Output is correct |
67 |
Correct |
418 ms |
69208 KB |
Output is correct |
68 |
Correct |
591 ms |
62032 KB |
Output is correct |
69 |
Correct |
906 ms |
62032 KB |
Output is correct |
70 |
Correct |
872 ms |
62212 KB |
Output is correct |
71 |
Correct |
751 ms |
62032 KB |
Output is correct |
72 |
Correct |
883 ms |
62032 KB |
Output is correct |
73 |
Correct |
731 ms |
62220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
15960 KB |
Output is correct |
2 |
Correct |
2 ms |
15960 KB |
Output is correct |
3 |
Correct |
2 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
16216 KB |
Output is correct |
5 |
Correct |
3 ms |
15960 KB |
Output is correct |
6 |
Correct |
3 ms |
15960 KB |
Output is correct |
7 |
Correct |
3 ms |
15960 KB |
Output is correct |
8 |
Correct |
3 ms |
15960 KB |
Output is correct |
9 |
Correct |
4 ms |
16216 KB |
Output is correct |
10 |
Correct |
3 ms |
16216 KB |
Output is correct |
11 |
Correct |
2 ms |
15960 KB |
Output is correct |
12 |
Correct |
2 ms |
15960 KB |
Output is correct |
13 |
Correct |
2 ms |
15960 KB |
Output is correct |
14 |
Correct |
2 ms |
15960 KB |
Output is correct |
15 |
Correct |
4 ms |
15960 KB |
Output is correct |
16 |
Correct |
4 ms |
16020 KB |
Output is correct |
17 |
Correct |
3 ms |
15960 KB |
Output is correct |
18 |
Correct |
3 ms |
15960 KB |
Output is correct |
19 |
Correct |
4 ms |
16268 KB |
Output is correct |
20 |
Correct |
4 ms |
11864 KB |
Output is correct |
21 |
Correct |
3 ms |
11864 KB |
Output is correct |
22 |
Correct |
3 ms |
11864 KB |
Output is correct |
23 |
Correct |
3 ms |
11864 KB |
Output is correct |
24 |
Correct |
4 ms |
12120 KB |
Output is correct |
25 |
Correct |
15 ms |
13912 KB |
Output is correct |
26 |
Correct |
18 ms |
13400 KB |
Output is correct |
27 |
Correct |
18 ms |
13400 KB |
Output is correct |
28 |
Correct |
24 ms |
13656 KB |
Output is correct |
29 |
Correct |
23 ms |
13400 KB |
Output is correct |
30 |
Correct |
4 ms |
15960 KB |
Output is correct |
31 |
Correct |
739 ms |
117196 KB |
Output is correct |
32 |
Correct |
907 ms |
115408 KB |
Output is correct |
33 |
Correct |
685 ms |
113320 KB |
Output is correct |
34 |
Correct |
820 ms |
116136 KB |
Output is correct |
35 |
Correct |
482 ms |
107020 KB |
Output is correct |
36 |
Correct |
483 ms |
106836 KB |
Output is correct |
37 |
Correct |
740 ms |
106576 KB |
Output is correct |
38 |
Correct |
724 ms |
106864 KB |
Output is correct |
39 |
Correct |
711 ms |
106996 KB |
Output is correct |
40 |
Correct |
663 ms |
107336 KB |
Output is correct |
41 |
Correct |
672 ms |
110644 KB |
Output is correct |
42 |
Correct |
769 ms |
110548 KB |
Output is correct |
43 |
Correct |
584 ms |
110500 KB |
Output is correct |
44 |
Correct |
765 ms |
109904 KB |
Output is correct |
45 |
Correct |
703 ms |
118432 KB |
Output is correct |
46 |
Correct |
2 ms |
11864 KB |
Output is correct |
47 |
Correct |
3 ms |
11864 KB |
Output is correct |
48 |
Correct |
2 ms |
11864 KB |
Output is correct |
49 |
Correct |
2 ms |
11864 KB |
Output is correct |
50 |
Correct |
663 ms |
107216 KB |
Output is correct |
51 |
Correct |
699 ms |
107436 KB |
Output is correct |
52 |
Correct |
558 ms |
107344 KB |
Output is correct |
53 |
Correct |
698 ms |
107412 KB |
Output is correct |
54 |
Correct |
562 ms |
105448 KB |
Output is correct |
55 |
Correct |
575 ms |
105276 KB |
Output is correct |
56 |
Correct |
519 ms |
105376 KB |
Output is correct |
57 |
Correct |
722 ms |
105276 KB |
Output is correct |
58 |
Correct |
409 ms |
120964 KB |
Output is correct |
59 |
Correct |
415 ms |
120800 KB |
Output is correct |
60 |
Correct |
320 ms |
120900 KB |
Output is correct |
61 |
Correct |
420 ms |
120956 KB |
Output is correct |
62 |
Correct |
427 ms |
106700 KB |
Output is correct |
63 |
Correct |
449 ms |
106660 KB |
Output is correct |
64 |
Correct |
369 ms |
106720 KB |
Output is correct |
65 |
Correct |
500 ms |
106648 KB |
Output is correct |
66 |
Correct |
2 ms |
13912 KB |
Output is correct |
67 |
Correct |
2 ms |
15960 KB |
Output is correct |
68 |
Correct |
3 ms |
15960 KB |
Output is correct |
69 |
Correct |
3 ms |
15960 KB |
Output is correct |
70 |
Correct |
3 ms |
16008 KB |
Output is correct |
71 |
Correct |
3 ms |
15960 KB |
Output is correct |
72 |
Correct |
4 ms |
16216 KB |
Output is correct |
73 |
Correct |
17 ms |
17868 KB |
Output is correct |
74 |
Correct |
382 ms |
122164 KB |
Output is correct |
75 |
Correct |
411 ms |
122192 KB |
Output is correct |
76 |
Correct |
351 ms |
122312 KB |
Output is correct |
77 |
Correct |
443 ms |
122364 KB |
Output is correct |
78 |
Correct |
448 ms |
69256 KB |
Output is correct |
79 |
Correct |
458 ms |
69188 KB |
Output is correct |
80 |
Correct |
442 ms |
69260 KB |
Output is correct |
81 |
Correct |
512 ms |
69200 KB |
Output is correct |
82 |
Correct |
451 ms |
69168 KB |
Output is correct |
83 |
Correct |
472 ms |
69200 KB |
Output is correct |
84 |
Correct |
922 ms |
122256 KB |
Output is correct |
85 |
Correct |
969 ms |
122448 KB |
Output is correct |
86 |
Correct |
965 ms |
122144 KB |
Output is correct |
87 |
Correct |
1031 ms |
122524 KB |
Output is correct |
88 |
Correct |
892 ms |
122172 KB |
Output is correct |
89 |
Correct |
975 ms |
122584 KB |
Output is correct |
90 |
Correct |
2 ms |
15960 KB |
Output is correct |
91 |
Correct |
3 ms |
15960 KB |
Output is correct |
92 |
Correct |
3 ms |
15960 KB |
Output is correct |
93 |
Correct |
3 ms |
15960 KB |
Output is correct |
94 |
Correct |
3 ms |
16024 KB |
Output is correct |
95 |
Correct |
4 ms |
16216 KB |
Output is correct |
96 |
Correct |
19 ms |
17496 KB |
Output is correct |
97 |
Correct |
434 ms |
108204 KB |
Output is correct |
98 |
Correct |
445 ms |
108112 KB |
Output is correct |
99 |
Correct |
400 ms |
108280 KB |
Output is correct |
100 |
Correct |
455 ms |
108368 KB |
Output is correct |
101 |
Correct |
640 ms |
62032 KB |
Output is correct |
102 |
Correct |
904 ms |
62040 KB |
Output is correct |
103 |
Correct |
910 ms |
62216 KB |
Output is correct |
104 |
Correct |
845 ms |
62220 KB |
Output is correct |
105 |
Correct |
1035 ms |
62036 KB |
Output is correct |
106 |
Correct |
871 ms |
62288 KB |
Output is correct |
107 |
Correct |
1388 ms |
108112 KB |
Output is correct |
108 |
Correct |
2048 ms |
108112 KB |
Output is correct |
109 |
Correct |
1956 ms |
108112 KB |
Output is correct |
110 |
Correct |
1830 ms |
108256 KB |
Output is correct |
111 |
Correct |
2331 ms |
108288 KB |
Output is correct |
112 |
Correct |
1916 ms |
108112 KB |
Output is correct |
113 |
Correct |
532 ms |
65104 KB |
Output is correct |
114 |
Correct |
631 ms |
66128 KB |
Output is correct |
115 |
Correct |
585 ms |
66128 KB |
Output is correct |
116 |
Correct |
617 ms |
66628 KB |
Output is correct |
117 |
Correct |
558 ms |
66896 KB |
Output is correct |
118 |
Correct |
613 ms |
65756 KB |
Output is correct |
119 |
Correct |
862 ms |
62296 KB |
Output is correct |
120 |
Correct |
870 ms |
62296 KB |
Output is correct |
121 |
Correct |
923 ms |
62096 KB |
Output is correct |
122 |
Correct |
894 ms |
62544 KB |
Output is correct |
123 |
Correct |
845 ms |
62288 KB |
Output is correct |
124 |
Correct |
776 ms |
62288 KB |
Output is correct |
125 |
Correct |
516 ms |
63824 KB |
Output is correct |
126 |
Correct |
688 ms |
63280 KB |
Output is correct |
127 |
Correct |
610 ms |
63568 KB |
Output is correct |
128 |
Correct |
610 ms |
63956 KB |
Output is correct |
129 |
Correct |
634 ms |
63312 KB |
Output is correct |
130 |
Correct |
609 ms |
64232 KB |
Output is correct |
131 |
Correct |
521 ms |
66628 KB |
Output is correct |
132 |
Correct |
538 ms |
67916 KB |
Output is correct |
133 |
Correct |
624 ms |
66292 KB |
Output is correct |
134 |
Correct |
556 ms |
62288 KB |
Output is correct |
135 |
Correct |
796 ms |
62276 KB |
Output is correct |
136 |
Correct |
694 ms |
62288 KB |
Output is correct |
137 |
Correct |
709 ms |
62288 KB |
Output is correct |
138 |
Correct |
710 ms |
62268 KB |
Output is correct |
139 |
Correct |
668 ms |
62288 KB |
Output is correct |
140 |
Correct |
571 ms |
61572 KB |
Output is correct |
141 |
Correct |
628 ms |
61572 KB |
Output is correct |
142 |
Correct |
586 ms |
61512 KB |
Output is correct |
143 |
Correct |
630 ms |
61568 KB |
Output is correct |
144 |
Correct |
545 ms |
61492 KB |
Output is correct |
145 |
Correct |
384 ms |
69196 KB |
Output is correct |
146 |
Correct |
428 ms |
69184 KB |
Output is correct |
147 |
Correct |
435 ms |
69200 KB |
Output is correct |
148 |
Correct |
417 ms |
69196 KB |
Output is correct |
149 |
Correct |
398 ms |
69452 KB |
Output is correct |
150 |
Correct |
418 ms |
69208 KB |
Output is correct |
151 |
Correct |
591 ms |
62032 KB |
Output is correct |
152 |
Correct |
906 ms |
62032 KB |
Output is correct |
153 |
Correct |
872 ms |
62212 KB |
Output is correct |
154 |
Correct |
751 ms |
62032 KB |
Output is correct |
155 |
Correct |
883 ms |
62032 KB |
Output is correct |
156 |
Correct |
731 ms |
62220 KB |
Output is correct |
157 |
Correct |
1036 ms |
116188 KB |
Output is correct |
158 |
Correct |
1052 ms |
116816 KB |
Output is correct |
159 |
Correct |
1218 ms |
115984 KB |
Output is correct |
160 |
Correct |
1326 ms |
114868 KB |
Output is correct |
161 |
Correct |
1225 ms |
117640 KB |
Output is correct |
162 |
Correct |
1313 ms |
117328 KB |
Output is correct |
163 |
Correct |
2057 ms |
108236 KB |
Output is correct |
164 |
Correct |
1988 ms |
108368 KB |
Output is correct |
165 |
Correct |
2123 ms |
107804 KB |
Output is correct |
166 |
Correct |
2069 ms |
108460 KB |
Output is correct |
167 |
Correct |
2192 ms |
108256 KB |
Output is correct |
168 |
Correct |
1983 ms |
107456 KB |
Output is correct |
169 |
Correct |
1341 ms |
110420 KB |
Output is correct |
170 |
Correct |
1546 ms |
109472 KB |
Output is correct |
171 |
Correct |
1570 ms |
109468 KB |
Output is correct |
172 |
Correct |
1485 ms |
110416 KB |
Output is correct |
173 |
Correct |
1431 ms |
111440 KB |
Output is correct |
174 |
Correct |
1438 ms |
112072 KB |
Output is correct |
175 |
Correct |
1213 ms |
116852 KB |
Output is correct |
176 |
Correct |
1213 ms |
117660 KB |
Output is correct |
177 |
Correct |
1346 ms |
121760 KB |
Output is correct |
178 |
Correct |
1512 ms |
108808 KB |
Output is correct |
179 |
Correct |
1805 ms |
108836 KB |
Output is correct |
180 |
Correct |
1760 ms |
108748 KB |
Output is correct |
181 |
Correct |
1773 ms |
107356 KB |
Output is correct |
182 |
Correct |
1736 ms |
107344 KB |
Output is correct |
183 |
Correct |
1632 ms |
108804 KB |
Output is correct |
184 |
Correct |
1303 ms |
105276 KB |
Output is correct |
185 |
Correct |
1332 ms |
105448 KB |
Output is correct |
186 |
Correct |
1288 ms |
105452 KB |
Output is correct |
187 |
Correct |
1381 ms |
105444 KB |
Output is correct |
188 |
Correct |
1231 ms |
105280 KB |
Output is correct |