oj.uz

Submission #1031545

# Submission time Handle Problem Language Result Execution time Memory
1031545 2024-07-23T00:34:40 Z sleepntsheep Tourism (JOI23_tourism) C
100 / 100
 1101 ms 30196 KB 
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include <stdio.h>
#include <stdlib.h>

inline 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)

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

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

int fw[MM];
inline void fw_add(unsigned p, int k) {
  for (; p < sizeof fw / sizeof *fw; p |= p + 1)
    fw[p] += k;
}
inline int fw_sum(int p) {
  int 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]] = 0;
    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);
  free(candidates);
  for (int i = 0; i < N; ++i)
      free(Occ[i]), free(adj[i]);
  for (int i = 0; i < Q; ++i)
    printf("%d\n", Ans[i] + 1);
  return 0;
}

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

Compilation message

tourism.c: In function 'main':
tourism.c:241:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:243:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |     scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:246:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:249:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  249 |     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 344 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 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 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 2 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 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 428 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 344 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 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 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 2 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 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 428 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 856 KB Output is correct
31 Correct 6 ms 784 KB Output is correct
32 Correct 8 ms 860 KB Output is correct
33 Correct 9 ms 948 KB Output is correct
34 Correct 8 ms 856 KB Output is correct
35 Correct 8 ms 860 KB Output is correct
36 Correct 10 ms 856 KB Output is correct
37 Correct 8 ms 860 KB Output is correct
38 Correct 6 ms 860 KB Output is correct
39 Correct 6 ms 1092 KB Output is correct
40 Correct 6 ms 860 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 6 ms 1116 KB Output is correct
43 Correct 6 ms 860 KB Output is correct
44 Correct 7 ms 860 KB Output is correct
45 Correct 7 ms 1028 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 7 ms 948 KB Output is correct
48 Correct 7 ms 856 KB Output is correct
49 Correct 7 ms 1032 KB Output is correct
50 Correct 6 ms 860 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 1012 KB Output is correct
53 Correct 8 ms 860 KB Output is correct
54 Correct 6 ms 1116 KB Output is correct
55 Correct 6 ms 1036 KB Output is correct
56 Correct 1 ms 540 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 8 ms 952 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 459 ms 18936 KB Output is correct
5 Correct 310 ms 22412 KB Output is correct
6 Correct 424 ms 25764 KB Output is correct
7 Correct 563 ms 29964 KB Output is correct
8 Correct 549 ms 29840 KB Output is correct
9 Correct 525 ms 29856 KB Output is correct
10 Correct 558 ms 29944 KB Output is correct
11 Correct 530 ms 29832 KB Output is correct
12 Correct 308 ms 29340 KB Output is correct
13 Correct 274 ms 29520 KB Output is correct
14 Correct 288 ms 29520 KB Output is correct
15 Correct 34 ms 15444 KB Output is correct
16 Correct 601 ms 30196 KB Output is correct
17 Correct 46 ms 4812 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 418 ms 11868 KB Output is correct
3 Correct 692 ms 13972 KB Output is correct
4 Correct 516 ms 14460 KB Output is correct
5 Correct 784 ms 20904 KB Output is correct
6 Correct 823 ms 20944 KB Output is correct
7 Correct 828 ms 21152 KB Output is correct
8 Correct 860 ms 20980 KB Output is correct
9 Correct 819 ms 20900 KB Output is correct
10 Correct 832 ms 20988 KB Output is correct
11 Correct 824 ms 21148 KB Output is correct
12 Correct 860 ms 21316 KB Output is correct
13 Correct 898 ms 21404 KB Output is correct
14 Correct 878 ms 22172 KB Output is correct
15 Correct 896 ms 24564 KB Output is correct
16 Correct 889 ms 21500 KB Output is correct
17 Correct 824 ms 21404 KB Output is correct
18 Correct 804 ms 21404 KB Output is correct
19 Correct 929 ms 20064 KB Output is correct
20 Correct 865 ms 20064 KB Output is correct
21 Correct 935 ms 20188 KB Output is correct
22 Correct 951 ms 20604 KB Output is correct
23 Correct 913 ms 20524 KB Output is correct
24 Correct 897 ms 20188 KB Output is correct
25 Correct 901 ms 20436 KB Output is correct
26 Correct 890 ms 20400 KB Output is correct
27 Correct 949 ms 20192 KB Output is correct
28 Correct 950 ms 20320 KB Output is correct
29 Correct 965 ms 20448 KB Output is correct
30 Correct 920 ms 20364 KB Output is correct
31 Correct 969 ms 20820 KB Output is correct
32 Correct 977 ms 21076 KB Output is correct
33 Correct 931 ms 22232 KB Output is correct
34 Correct 1101 ms 23908 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 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 665 ms 16284 KB Output is correct
5 Correct 738 ms 16612 KB Output is correct
6 Correct 754 ms 21836 KB Output is correct
7 Correct 857 ms 24308 KB Output is correct
8 Correct 786 ms 24440 KB Output is correct
9 Correct 772 ms 24376 KB Output is correct
10 Correct 811 ms 24320 KB Output is correct
11 Correct 761 ms 24304 KB Output is correct
12 Correct 825 ms 24304 KB Output is correct
13 Correct 783 ms 24304 KB Output is correct
14 Correct 51 ms 4808 KB Output is correct

Subtask #6
41.0 / 41.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 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 2 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 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 428 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 856 KB Output is correct
31 Correct 6 ms 784 KB Output is correct
32 Correct 8 ms 860 KB Output is correct
33 Correct 9 ms 948 KB Output is correct
34 Correct 8 ms 856 KB Output is correct
35 Correct 8 ms 860 KB Output is correct
36 Correct 10 ms 856 KB Output is correct
37 Correct 8 ms 860 KB Output is correct
38 Correct 6 ms 860 KB Output is correct
39 Correct 6 ms 1092 KB Output is correct
40 Correct 6 ms 860 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 6 ms 1116 KB Output is correct
43 Correct 6 ms 860 KB Output is correct
44 Correct 7 ms 860 KB Output is correct
45 Correct 7 ms 1028 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 7 ms 948 KB Output is correct
48 Correct 7 ms 856 KB Output is correct
49 Correct 7 ms 1032 KB Output is correct
50 Correct 6 ms 860 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 1012 KB Output is correct
53 Correct 8 ms 860 KB Output is correct
54 Correct 6 ms 1116 KB Output is correct
55 Correct 6 ms 1036 KB Output is correct
56 Correct 1 ms 540 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 8 ms 952 KB Output is correct
59 Correct 1 ms 504 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 459 ms 18936 KB Output is correct
63 Correct 310 ms 22412 KB Output is correct
64 Correct 424 ms 25764 KB Output is correct
65 Correct 563 ms 29964 KB Output is correct
66 Correct 549 ms 29840 KB Output is correct
67 Correct 525 ms 29856 KB Output is correct
68 Correct 558 ms 29944 KB Output is correct
69 Correct 530 ms 29832 KB Output is correct
70 Correct 308 ms 29340 KB Output is correct
71 Correct 274 ms 29520 KB Output is correct
72 Correct 288 ms 29520 KB Output is correct
73 Correct 34 ms 15444 KB Output is correct
74 Correct 601 ms 30196 KB Output is correct
75 Correct 46 ms 4812 KB Output is correct
76 Correct 0 ms 344 KB Output is correct
77 Correct 418 ms 11868 KB Output is correct
78 Correct 692 ms 13972 KB Output is correct
79 Correct 516 ms 14460 KB Output is correct
80 Correct 784 ms 20904 KB Output is correct
81 Correct 823 ms 20944 KB Output is correct
82 Correct 828 ms 21152 KB Output is correct
83 Correct 860 ms 20980 KB Output is correct
84 Correct 819 ms 20900 KB Output is correct
85 Correct 832 ms 20988 KB Output is correct
86 Correct 824 ms 21148 KB Output is correct
87 Correct 860 ms 21316 KB Output is correct
88 Correct 898 ms 21404 KB Output is correct
89 Correct 878 ms 22172 KB Output is correct
90 Correct 896 ms 24564 KB Output is correct
91 Correct 889 ms 21500 KB Output is correct
92 Correct 824 ms 21404 KB Output is correct
93 Correct 804 ms 21404 KB Output is correct
94 Correct 929 ms 20064 KB Output is correct
95 Correct 865 ms 20064 KB Output is correct
96 Correct 935 ms 20188 KB Output is correct
97 Correct 951 ms 20604 KB Output is correct
98 Correct 913 ms 20524 KB Output is correct
99 Correct 897 ms 20188 KB Output is correct
100 Correct 901 ms 20436 KB Output is correct
101 Correct 890 ms 20400 KB Output is correct
102 Correct 949 ms 20192 KB Output is correct
103 Correct 950 ms 20320 KB Output is correct
104 Correct 965 ms 20448 KB Output is correct
105 Correct 920 ms 20364 KB Output is correct
106 Correct 969 ms 20820 KB Output is correct
107 Correct 977 ms 21076 KB Output is correct
108 Correct 931 ms 22232 KB Output is correct
109 Correct 1101 ms 23908 KB Output is correct
110 Correct 0 ms 344 KB Output is correct
111 Correct 1 ms 348 KB Output is correct
112 Correct 1 ms 604 KB Output is correct
113 Correct 665 ms 16284 KB Output is correct
114 Correct 738 ms 16612 KB Output is correct
115 Correct 754 ms 21836 KB Output is correct
116 Correct 857 ms 24308 KB Output is correct
117 Correct 786 ms 24440 KB Output is correct
118 Correct 772 ms 24376 KB Output is correct
119 Correct 811 ms 24320 KB Output is correct
120 Correct 761 ms 24304 KB Output is correct
121 Correct 825 ms 24304 KB Output is correct
122 Correct 783 ms 24304 KB Output is correct
123 Correct 51 ms 4808 KB Output is correct
124 Correct 713 ms 23388 KB Output is correct
125 Correct 505 ms 20304 KB Output is correct
126 Correct 844 ms 24348 KB Output is correct
127 Correct 831 ms 24316 KB Output is correct
128 Correct 869 ms 24228 KB Output is correct
129 Correct 800 ms 24360 KB Output is correct
130 Correct 836 ms 24360 KB Output is correct
131 Correct 692 ms 29016 KB Output is correct
132 Correct 700 ms 29784 KB Output is correct
133 Correct 674 ms 27632 KB Output is correct
134 Correct 930 ms 23516 KB Output is correct
135 Correct 946 ms 23568 KB Output is correct
136 Correct 877 ms 23388 KB Output is correct
137 Correct 492 ms 24216 KB Output is correct
138 Correct 466 ms 24132 KB Output is correct
139 Correct 501 ms 24256 KB Output is correct
140 Correct 485 ms 24312 KB Output is correct
141 Correct 507 ms 24244 KB Output is correct
142 Correct 499 ms 24152 KB Output is correct
143 Correct 37 ms 9296 KB Output is correct
144 Correct 868 ms 24744 KB Output is correct