oj.uz

Submission #1031541

# Submission time Handle Problem Language Result Execution time Memory
1031541 2024-07-23T00:08:16 Z sleepntsheep Tourism (JOI23_tourism) C
100 / 100
 1010 ms 27404 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <stdio.h>
#include <stdlib.h>

void pus_(int **eh, int *eo, int x) {
  int o = eo[0]++;
  if (o == 0)
    eh[0] = (int*)malloc(2 * sizeof **eh);
  else if ((o & (o - 1)) == 0)
    eh[0] = (int*)realloc(eh[0], 2 * o * sizeof **eh);
  eh[0][o++] = x;
}
#define pus(eh, eo, x) pus_(&(eh), &(eo), x)

int min(int i, int j) { return i < j ? i : j; }
int max(int i, int j) { return i > j ? i : j; }

#define QQ 100000
#define NN 100000
#define MM 100000

int fw[MM];
void fw_add(int p, int k) {
  for (; p < sizeof fw / sizeof *fw; p |= p + 1)
    fw[p] += k;
}
long long fw_sum(int p) {
  long long z = 0;
  for (++p; p > 0; p &= p - 1)
    z += fw[p - 1];
  return z;
}

int tout[NN], Ans[QQ], N, M, Q, C[MM], L[QQ], R[QQ], X[NN], Y[NN], Freq[NN], *Occ[NN];

int *adj[NN], deg[NN], dfn[NN], timer, dep[NN], jmp[NN], par[NN];
void tree_link(int u, int v) {
  pus(adj[u], deg[u], v);
}
void tree_link_bi(int u, int v) {
    tree_link(u, v), tree_link(v, u);
}
void dfs(int u, int p) {
  dep[u] = dep[par[u] = p] + 1;
  jmp[u] = (dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]]) ? jmp[jmp[p]] : p;
  dfn[u] = timer++;
  for (int j = 0; j < deg[u]; ++j)
    if (adj[u][j] - p)
      dfs(adj[u][j], u);
  tout[u] = timer - 1;
}
int lca(int u, int v) {
  if (dep[u] < dep[v])
    return lca(v, u);
  while (dep[u] > dep[v])
    u = (dep[jmp[u]] >= dep[v]) ? jmp[u] : par[u];
  while (u - v)
    if (jmp[u] == jmp[v])
      u = par[u], v = par[v];
    else
      u = jmp[u], v = jmp[v];
  return u;
}

int *vtadj[NN], *vtw[NN], vtdeg[NN], vtdeg2[NN];
void virtual_link(int u, int v, int w) {
    pus(vtadj[u], vtdeg[u], v);
    --vtdeg[u];
    pus(vtw[u], vtdeg[u], w);
}
void virtual_link_bi(int u, int v, int w) { virtual_link(u, v, w), virtual_link(v, u, w); }

int Compar_Dfn(const void *i, const void *j) {
  return dfn[*(const int *)i] - dfn[*(const int *)j];
}

/* in virtual tree, X[u] stores highest k < m such that C[k] == u,
 *              analogously, Y[u] = stores lowest k > m such that C[k] == u
 * this is needed because, we take edge (x, y, w) in virtual tree (rooted at
 * C[m]) if query_l <= x or query_r >= y
 *
 * note that if u is parent of v in virtual tree, even if v's timer more
 * permissive than u's timer, we need to take v anyway, so a node's timer need
 * to be set at least at strict as it's stricted children */
int vt_up[NN]; /*weight of u, par[u] */
int add_all = 0;

/* note on how to build virtual tree - sort all vertices in dfn order, insert
 * lca of every consecutive element, uniqueify the new Vertex List, make the
 * tree?? */
void vtdfs(int u, int p, int pw, int m) {
  add_all += pw;
  vt_up[u] = pw;
  /* find upperbound(Occ[u], m); */
  int lb = -1, ub = Freq[u];
  while (ub - lb > 1) {
    int mid = lb + (ub - lb) / 2;
    if (Occ[u][mid] > m)
      ub = mid;
    else
      lb = mid;
  }
  if (ub < Freq[u])
    Y[u] = Occ[u][ub];
  if ((ub && Occ[u][--ub] < m) || (ub && Occ[u][--ub] < m))
      X[u] = Occ[u][ub];

  for (int j = 0; j < vtdeg[u]; ++j)
    if (vtadj[u][j] != p) {
      vtdfs(vtadj[u][j], u, vtw[u][j], m);
      X[u] = max(X[u], X[vtadj[u][j]]);
      Y[u] = min(Y[u], Y[vtadj[u][j]]);
    }
}

int Compar_Queries_QL_Decreasing(const void*a,const void*b) {
    return L[*(const int*)b] - L[*(const int*)a];
}

int Compar_Edges_X_Decreasing(const void*a,const void*b) {
    return X[*(const int*)b] - X[*(const int*)a];
}

void rev(int *a, int n) {
    int t;
    for (int l = 0, r = n - 1; l < r; ++l, --r)
        t = a[l], a[l] = a[r], a[r] = t;
}

int mark[NN] = {0}, dnc_timer = 0;

void dnc(
    int l, int r, int *candidates,
    int count_candidates) {
  if (l >= r)
    return; /* ignore l=r because answer is always 1 (ql==qr)*/
  int m = l + (r - l) / 2;

  /* V = set of vertices in virtual tree , ord = |V| */
  /* build a virtual tree for all node u that some l <= k <= r, C[k] = u */
  /* collect all interested nodes */
  int *V = NULL, ord = 0;
  ++dnc_timer;
  for (int i = l; i <= r; ++i)
    if (dnc_timer != mark[C[i]])
       (mark[C[i]] = dnc_timer),
       pus(V, ord, C[i]);

  qsort(V, ord, sizeof *V, Compar_Dfn);
  for (int orig_ord = ord, lc, i = 1; i < orig_ord; ++i)
    if (dnc_timer != mark[lc = lca(V[i], V[i - 1])])
      pus(V, ord, lc), mark[lc] = dnc_timer;
  qsort(V, ord, sizeof *V, Compar_Dfn);

  /* clear global related to virtual tree */
  for (int i = 0; i < ord; ++i) {
      free(vtadj[V[i]]);
      free(vtw[V[i]]);
      vtadj[V[i]] = vtw[V[i]] = NULL;
      vtdeg[V[i]] = NULL;
      add_all = 0;
  }

  /* build vt */
  static int stack[NN << 1], top;
  top = 0;
  for (int i = 0; i < ord; ++i) {
      int u = V[i];
      while (top && !(dfn[stack[top - 1]] <= dfn[u] &&
                  tout[u] <= tout[stack[top - 1]]))
          --top;
      if (top)
          virtual_link_bi(stack[top - 1], u, dep[u] - dep[stack[top - 1]]);
      stack[top++] = u;
  }

  /* do dfs on vt to calculate X and Y */
  for (int i = 0; i < ord; ++i)
    X[V[i]] = -2, Y[V[i]] = 1e9 + 2;

  vtdfs(C[m], -1, 0, m);

  /* collect all active queries, one that contain m (ql <= m <= qr) */
  int *active = NULL, nactive = 0,
      *Xt = NULL, nXt = 0,
      *right = NULL, nright = 0;
  for (int i = 0; i < count_candidates; ++i) {
    int j = candidates[i];
    if (L[j] <= m && m <= R[j])
      pus(active, nactive, j);
    else if (R[j] < m)
      pus(Xt, nXt, j);
    else if (L[j] > m)
      pus(right, nright, j);
  }

  /*
   * we add w to queries that ql <= x or y <= qr
   * that is , ql <= x , exclusive or (ql > x and y <= qr) */

  /* sort active by ql */
  /* ql <= x */
  qsort(active, nactive, sizeof(int), Compar_Queries_QL_Decreasing);
  qsort(V, ord, sizeof(int), Compar_Edges_X_Decreasing);

  int pi = 0, sum = 0;
  for (int i = 0; i < nactive; ++i) {
      int qi = active[i];
      while (pi < ord && X[V[pi]] >= L[qi]) 
          sum += vt_up[V[pi++]];
      Ans[qi] += sum;
  }

  /* mutex, ql > x and y <= qr */
  rev(active, nactive);
  rev(V, ord);
  pi = 0;
  for (int i = 0; i < nactive; ++i) {
      int qi = active[i];
      while (pi < ord && X[V[pi]] < L[qi])
          fw_add(Y[V[pi]], vt_up[V[pi]]), ++pi;
      Ans[qi] += fw_sum(R[qi]);
  }

  /* undo all fenwick upd (IM GONNA KILLL MYSELF AG IRUH */
  pi = 0;
  for (int i = 0; i < nactive; ++i) {
      int qi = active[i];
      while (pi < ord && X[V[pi]] < L[qi])
          fw_add(Y[V[pi]], -vt_up[V[pi]]), ++pi;
  }

  free(V);
  free(active);

  dnc(l, m, Xt, nXt);
  dnc(m + 1, r, right, nright);
  free(Xt);
  free(right);
}

int main() {
  scanf("%d%d%d", &N, &M, &Q);
  for (int i = 1, A, B; i < N; ++i)
    scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
  dfs(0, 0);
  for (int i = 0; i < M; ++i)
    scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
  int *candidates = (int*)malloc(sizeof*candidates * Q);
  for (int i = 0; i < Q; ++i)
    scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
  dnc(0, M - 1, candidates, Q);
  for (int i = 0; i < Q; ++i)
      printf("%d\n", Ans[i] + 1);
  free(candidates);
}

/*
 * https://codeforces.com/blog/entry/114003?#comment-1015100
 *
 * DNC
 */

Compilation message

tourism.c: In function 'dnc':
tourism.c:160:19: warning: assignment to 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
  160 |       vtdeg[V[i]] = NULL;
      |                   ^
tourism.c: In function 'main':
tourism.c:243:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:245:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  245 |     scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:248:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  248 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:251:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |     scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 6 ms 860 KB Output is correct
31 Correct 6 ms 860 KB Output is correct
32 Correct 8 ms 860 KB Output is correct
33 Correct 8 ms 964 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 8 ms 972 KB Output is correct
36 Correct 8 ms 860 KB Output is correct
37 Correct 8 ms 972 KB Output is correct
38 Correct 6 ms 856 KB Output is correct
39 Correct 6 ms 856 KB Output is correct
40 Correct 6 ms 856 KB Output is correct
41 Correct 6 ms 1112 KB Output is correct
42 Correct 6 ms 860 KB Output is correct
43 Correct 6 ms 860 KB Output is correct
44 Correct 7 ms 1004 KB Output is correct
45 Correct 7 ms 860 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 7 ms 860 KB Output is correct
48 Correct 7 ms 860 KB Output is correct
49 Correct 7 ms 860 KB Output is correct
50 Correct 6 ms 856 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 988 KB Output is correct
53 Correct 6 ms 860 KB Output is correct
54 Correct 6 ms 988 KB Output is correct
55 Correct 5 ms 988 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 8 ms 920 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 423 ms 17244 KB Output is correct
5 Correct 277 ms 20620 KB Output is correct
6 Correct 401 ms 23596 KB Output is correct
7 Correct 505 ms 27404 KB Output is correct
8 Correct 506 ms 27192 KB Output is correct
9 Correct 516 ms 27164 KB Output is correct
10 Correct 526 ms 27208 KB Output is correct
11 Correct 550 ms 26972 KB Output is correct
12 Correct 265 ms 26704 KB Output is correct
13 Correct 277 ms 26828 KB Output is correct
14 Correct 279 ms 26828 KB Output is correct
15 Correct 31 ms 14168 KB Output is correct
16 Correct 559 ms 27292 KB Output is correct
17 Correct 43 ms 3528 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 405 ms 11080 KB Output is correct
3 Correct 635 ms 12832 KB Output is correct
4 Correct 492 ms 13240 KB Output is correct
5 Correct 784 ms 19008 KB Output is correct
6 Correct 759 ms 19136 KB Output is correct
7 Correct 779 ms 19336 KB Output is correct
8 Correct 764 ms 19140 KB Output is correct
9 Correct 806 ms 19316 KB Output is correct
10 Correct 770 ms 19360 KB Output is correct
11 Correct 778 ms 19544 KB Output is correct
12 Correct 782 ms 19360 KB Output is correct
13 Correct 789 ms 19616 KB Output is correct
14 Correct 829 ms 20144 KB Output is correct
15 Correct 869 ms 21932 KB Output is correct
16 Correct 787 ms 19616 KB Output is correct
17 Correct 776 ms 19612 KB Output is correct
18 Correct 788 ms 19608 KB Output is correct
19 Correct 886 ms 18520 KB Output is correct
20 Correct 845 ms 18744 KB Output is correct
21 Correct 812 ms 18480 KB Output is correct
22 Correct 850 ms 18640 KB Output is correct
23 Correct 914 ms 18640 KB Output is correct
24 Correct 885 ms 18636 KB Output is correct
25 Correct 862 ms 18644 KB Output is correct
26 Correct 897 ms 18696 KB Output is correct
27 Correct 894 ms 18632 KB Output is correct
28 Correct 866 ms 18528 KB Output is correct
29 Correct 891 ms 18532 KB Output is correct
30 Correct 868 ms 18696 KB Output is correct
31 Correct 913 ms 19032 KB Output is correct
32 Correct 909 ms 19040 KB Output is correct
33 Correct 927 ms 19936 KB Output is correct
34 Correct 1010 ms 21104 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 670 ms 14232 KB Output is correct
5 Correct 647 ms 14728 KB Output is correct
6 Correct 786 ms 19644 KB Output is correct
7 Correct 859 ms 21824 KB Output is correct
8 Correct 839 ms 21788 KB Output is correct
9 Correct 814 ms 21916 KB Output is correct
10 Correct 793 ms 21852 KB Output is correct
11 Correct 799 ms 22140 KB Output is correct
12 Correct 798 ms 21852 KB Output is correct
13 Correct 763 ms 21932 KB Output is correct
14 Correct 43 ms 3528 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 6 ms 860 KB Output is correct
31 Correct 6 ms 860 KB Output is correct
32 Correct 8 ms 860 KB Output is correct
33 Correct 8 ms 964 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 8 ms 972 KB Output is correct
36 Correct 8 ms 860 KB Output is correct
37 Correct 8 ms 972 KB Output is correct
38 Correct 6 ms 856 KB Output is correct
39 Correct 6 ms 856 KB Output is correct
40 Correct 6 ms 856 KB Output is correct
41 Correct 6 ms 1112 KB Output is correct
42 Correct 6 ms 860 KB Output is correct
43 Correct 6 ms 860 KB Output is correct
44 Correct 7 ms 1004 KB Output is correct
45 Correct 7 ms 860 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 7 ms 860 KB Output is correct
48 Correct 7 ms 860 KB Output is correct
49 Correct 7 ms 860 KB Output is correct
50 Correct 6 ms 856 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 988 KB Output is correct
53 Correct 6 ms 860 KB Output is correct
54 Correct 6 ms 988 KB Output is correct
55 Correct 5 ms 988 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 8 ms 920 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1 ms 408 KB Output is correct
62 Correct 423 ms 17244 KB Output is correct
63 Correct 277 ms 20620 KB Output is correct
64 Correct 401 ms 23596 KB Output is correct
65 Correct 505 ms 27404 KB Output is correct
66 Correct 506 ms 27192 KB Output is correct
67 Correct 516 ms 27164 KB Output is correct
68 Correct 526 ms 27208 KB Output is correct
69 Correct 550 ms 26972 KB Output is correct
70 Correct 265 ms 26704 KB Output is correct
71 Correct 277 ms 26828 KB Output is correct
72 Correct 279 ms 26828 KB Output is correct
73 Correct 31 ms 14168 KB Output is correct
74 Correct 559 ms 27292 KB Output is correct
75 Correct 43 ms 3528 KB Output is correct
76 Correct 0 ms 344 KB Output is correct
77 Correct 405 ms 11080 KB Output is correct
78 Correct 635 ms 12832 KB Output is correct
79 Correct 492 ms 13240 KB Output is correct
80 Correct 784 ms 19008 KB Output is correct
81 Correct 759 ms 19136 KB Output is correct
82 Correct 779 ms 19336 KB Output is correct
83 Correct 764 ms 19140 KB Output is correct
84 Correct 806 ms 19316 KB Output is correct
85 Correct 770 ms 19360 KB Output is correct
86 Correct 778 ms 19544 KB Output is correct
87 Correct 782 ms 19360 KB Output is correct
88 Correct 789 ms 19616 KB Output is correct
89 Correct 829 ms 20144 KB Output is correct
90 Correct 869 ms 21932 KB Output is correct
91 Correct 787 ms 19616 KB Output is correct
92 Correct 776 ms 19612 KB Output is correct
93 Correct 788 ms 19608 KB Output is correct
94 Correct 886 ms 18520 KB Output is correct
95 Correct 845 ms 18744 KB Output is correct
96 Correct 812 ms 18480 KB Output is correct
97 Correct 850 ms 18640 KB Output is correct
98 Correct 914 ms 18640 KB Output is correct
99 Correct 885 ms 18636 KB Output is correct
100 Correct 862 ms 18644 KB Output is correct
101 Correct 897 ms 18696 KB Output is correct
102 Correct 894 ms 18632 KB Output is correct
103 Correct 866 ms 18528 KB Output is correct
104 Correct 891 ms 18532 KB Output is correct
105 Correct 868 ms 18696 KB Output is correct
106 Correct 913 ms 19032 KB Output is correct
107 Correct 909 ms 19040 KB Output is correct
108 Correct 927 ms 19936 KB Output is correct
109 Correct 1010 ms 21104 KB Output is correct
110 Correct 0 ms 344 KB Output is correct
111 Correct 0 ms 348 KB Output is correct
112 Correct 2 ms 604 KB Output is correct
113 Correct 670 ms 14232 KB Output is correct
114 Correct 647 ms 14728 KB Output is correct
115 Correct 786 ms 19644 KB Output is correct
116 Correct 859 ms 21824 KB Output is correct
117 Correct 839 ms 21788 KB Output is correct
118 Correct 814 ms 21916 KB Output is correct
119 Correct 793 ms 21852 KB Output is correct
120 Correct 799 ms 22140 KB Output is correct
121 Correct 798 ms 21852 KB Output is correct
122 Correct 763 ms 21932 KB Output is correct
123 Correct 43 ms 3528 KB Output is correct
124 Correct 672 ms 20728 KB Output is correct
125 Correct 480 ms 18240 KB Output is correct
126 Correct 794 ms 21932 KB Output is correct
127 Correct 815 ms 21868 KB Output is correct
128 Correct 762 ms 21808 KB Output is correct
129 Correct 792 ms 21936 KB Output is correct
130 Correct 773 ms 21928 KB Output is correct
131 Correct 629 ms 26408 KB Output is correct
132 Correct 624 ms 27172 KB Output is correct
133 Correct 643 ms 25044 KB Output is correct
134 Correct 863 ms 21284 KB Output is correct
135 Correct 901 ms 20992 KB Output is correct
136 Correct 878 ms 20876 KB Output is correct
137 Correct 470 ms 21452 KB Output is correct
138 Correct 487 ms 21240 KB Output is correct
139 Correct 490 ms 21820 KB Output is correct
140 Correct 480 ms 21240 KB Output is correct
141 Correct 485 ms 21424 KB Output is correct
142 Correct 487 ms 21344 KB Output is correct
143 Correct 31 ms 8020 KB Output is correct
144 Correct 804 ms 21936 KB Output is correct