oj.uz

Submission #1031544

# Submission time Handle Problem Language Result Execution time Memory
1031544 2024-07-23T00:11:19 Z sleepntsheep Tourism (JOI23_tourism) C
100 / 100
 1082 ms 27316 KB 
#pragma GCC optimize("O3,unroll-loops")
#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(int p, int k) {
  for (; p < sizeof fw / sizeof *fw; p |= p + 1)
    fw[p] += k;
}
inline 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);
  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 'dnc':
tourism.c:157:17: warning: assignment to 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
  157 |     vtdeg[V[i]] = NULL;
      |                 ^
tourism.c: In function 'main':
tourism.c:239:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:241:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |     scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:244:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:247:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |     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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 600 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 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 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 1 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 2 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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 600 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 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 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 1 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 7 ms 864 KB Output is correct
31 Correct 7 ms 860 KB Output is correct
32 Correct 10 ms 984 KB Output is correct
33 Correct 9 ms 860 KB Output is correct
34 Correct 8 ms 956 KB Output is correct
35 Correct 9 ms 1112 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 860 KB Output is correct
39 Correct 9 ms 860 KB Output is correct
40 Correct 9 ms 1052 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 6 ms 856 KB Output is correct
43 Correct 6 ms 848 KB Output is correct
44 Correct 7 ms 860 KB Output is correct
45 Correct 8 ms 936 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 9 ms 856 KB Output is correct
48 Correct 10 ms 968 KB Output is correct
49 Correct 9 ms 856 KB Output is correct
50 Correct 6 ms 988 KB Output is correct
51 Correct 8 ms 860 KB Output is correct
52 Correct 6 ms 860 KB Output is correct
53 Correct 6 ms 860 KB Output is correct
54 Correct 9 ms 988 KB Output is correct
55 Correct 6 ms 860 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 964 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 467 ms 17068 KB Output is correct
5 Correct 363 ms 20624 KB Output is correct
6 Correct 530 ms 23924 KB Output is correct
7 Correct 581 ms 27128 KB Output is correct
8 Correct 631 ms 26972 KB Output is correct
9 Correct 587 ms 26968 KB Output is correct
10 Correct 595 ms 26864 KB Output is correct
11 Correct 623 ms 27080 KB Output is correct
12 Correct 322 ms 26700 KB Output is correct
13 Correct 296 ms 26764 KB Output is correct
14 Correct 288 ms 26760 KB Output is correct
15 Correct 34 ms 13912 KB Output is correct
16 Correct 627 ms 27316 KB Output is correct
17 Correct 68 ms 3284 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 420 ms 10852 KB Output is correct
3 Correct 737 ms 12876 KB Output is correct
4 Correct 588 ms 13568 KB Output is correct
5 Correct 938 ms 20688 KB Output is correct
6 Correct 847 ms 20788 KB Output is correct
7 Correct 851 ms 20872 KB Output is correct
8 Correct 864 ms 20760 KB Output is correct
9 Correct 940 ms 20888 KB Output is correct
10 Correct 1014 ms 21040 KB Output is correct
11 Correct 991 ms 21084 KB Output is correct
12 Correct 1035 ms 21088 KB Output is correct
13 Correct 963 ms 21396 KB Output is correct
14 Correct 996 ms 22156 KB Output is correct
15 Correct 995 ms 24208 KB Output is correct
16 Correct 1010 ms 21260 KB Output is correct
17 Correct 982 ms 21436 KB Output is correct
18 Correct 853 ms 21436 KB Output is correct
19 Correct 1026 ms 20004 KB Output is correct
20 Correct 1082 ms 20020 KB Output is correct
21 Correct 1042 ms 20132 KB Output is correct
22 Correct 1022 ms 19936 KB Output is correct
23 Correct 993 ms 20188 KB Output is correct
24 Correct 942 ms 20192 KB Output is correct
25 Correct 954 ms 20188 KB Output is correct
26 Correct 941 ms 20068 KB Output is correct
27 Correct 999 ms 20168 KB Output is correct
28 Correct 981 ms 20312 KB Output is correct
29 Correct 971 ms 20200 KB Output is correct
30 Correct 948 ms 20316 KB Output is correct
31 Correct 1002 ms 18860 KB Output is correct
32 Correct 1033 ms 19036 KB Output is correct
33 Correct 1068 ms 19804 KB Output is correct
34 Correct 1047 ms 21104 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 737 ms 14060 KB Output is correct
5 Correct 718 ms 14500 KB Output is correct
6 Correct 828 ms 19240 KB Output is correct
7 Correct 774 ms 21360 KB Output is correct
8 Correct 772 ms 21368 KB Output is correct
9 Correct 772 ms 21492 KB Output is correct
10 Correct 788 ms 21460 KB Output is correct
11 Correct 782 ms 21516 KB Output is correct
12 Correct 748 ms 21496 KB Output is correct
13 Correct 795 ms 21488 KB Output is correct
14 Correct 45 ms 3276 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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 600 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 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 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 1 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 7 ms 864 KB Output is correct
31 Correct 7 ms 860 KB Output is correct
32 Correct 10 ms 984 KB Output is correct
33 Correct 9 ms 860 KB Output is correct
34 Correct 8 ms 956 KB Output is correct
35 Correct 9 ms 1112 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 860 KB Output is correct
39 Correct 9 ms 860 KB Output is correct
40 Correct 9 ms 1052 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 6 ms 856 KB Output is correct
43 Correct 6 ms 848 KB Output is correct
44 Correct 7 ms 860 KB Output is correct
45 Correct 8 ms 936 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 9 ms 856 KB Output is correct
48 Correct 10 ms 968 KB Output is correct
49 Correct 9 ms 856 KB Output is correct
50 Correct 6 ms 988 KB Output is correct
51 Correct 8 ms 860 KB Output is correct
52 Correct 6 ms 860 KB Output is correct
53 Correct 6 ms 860 KB Output is correct
54 Correct 9 ms 988 KB Output is correct
55 Correct 6 ms 860 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 964 KB Output is correct
59 Correct 1 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 467 ms 17068 KB Output is correct
63 Correct 363 ms 20624 KB Output is correct
64 Correct 530 ms 23924 KB Output is correct
65 Correct 581 ms 27128 KB Output is correct
66 Correct 631 ms 26972 KB Output is correct
67 Correct 587 ms 26968 KB Output is correct
68 Correct 595 ms 26864 KB Output is correct
69 Correct 623 ms 27080 KB Output is correct
70 Correct 322 ms 26700 KB Output is correct
71 Correct 296 ms 26764 KB Output is correct
72 Correct 288 ms 26760 KB Output is correct
73 Correct 34 ms 13912 KB Output is correct
74 Correct 627 ms 27316 KB Output is correct
75 Correct 68 ms 3284 KB Output is correct
76 Correct 1 ms 348 KB Output is correct
77 Correct 420 ms 10852 KB Output is correct
78 Correct 737 ms 12876 KB Output is correct
79 Correct 588 ms 13568 KB Output is correct
80 Correct 938 ms 20688 KB Output is correct
81 Correct 847 ms 20788 KB Output is correct
82 Correct 851 ms 20872 KB Output is correct
83 Correct 864 ms 20760 KB Output is correct
84 Correct 940 ms 20888 KB Output is correct
85 Correct 1014 ms 21040 KB Output is correct
86 Correct 991 ms 21084 KB Output is correct
87 Correct 1035 ms 21088 KB Output is correct
88 Correct 963 ms 21396 KB Output is correct
89 Correct 996 ms 22156 KB Output is correct
90 Correct 995 ms 24208 KB Output is correct
91 Correct 1010 ms 21260 KB Output is correct
92 Correct 982 ms 21436 KB Output is correct
93 Correct 853 ms 21436 KB Output is correct
94 Correct 1026 ms 20004 KB Output is correct
95 Correct 1082 ms 20020 KB Output is correct
96 Correct 1042 ms 20132 KB Output is correct
97 Correct 1022 ms 19936 KB Output is correct
98 Correct 993 ms 20188 KB Output is correct
99 Correct 942 ms 20192 KB Output is correct
100 Correct 954 ms 20188 KB Output is correct
101 Correct 941 ms 20068 KB Output is correct
102 Correct 999 ms 20168 KB Output is correct
103 Correct 981 ms 20312 KB Output is correct
104 Correct 971 ms 20200 KB Output is correct
105 Correct 948 ms 20316 KB Output is correct
106 Correct 1002 ms 18860 KB Output is correct
107 Correct 1033 ms 19036 KB Output is correct
108 Correct 1068 ms 19804 KB Output is correct
109 Correct 1047 ms 21104 KB Output is correct
110 Correct 1 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 737 ms 14060 KB Output is correct
114 Correct 718 ms 14500 KB Output is correct
115 Correct 828 ms 19240 KB Output is correct
116 Correct 774 ms 21360 KB Output is correct
117 Correct 772 ms 21368 KB Output is correct
118 Correct 772 ms 21492 KB Output is correct
119 Correct 788 ms 21460 KB Output is correct
120 Correct 782 ms 21516 KB Output is correct
121 Correct 748 ms 21496 KB Output is correct
122 Correct 795 ms 21488 KB Output is correct
123 Correct 45 ms 3276 KB Output is correct
124 Correct 666 ms 20504 KB Output is correct
125 Correct 516 ms 18240 KB Output is correct
126 Correct 828 ms 21524 KB Output is correct
127 Correct 818 ms 21440 KB Output is correct
128 Correct 829 ms 21540 KB Output is correct
129 Correct 810 ms 21444 KB Output is correct
130 Correct 832 ms 21472 KB Output is correct
131 Correct 673 ms 26012 KB Output is correct
132 Correct 632 ms 26900 KB Output is correct
133 Correct 668 ms 24412 KB Output is correct
134 Correct 934 ms 20632 KB Output is correct
135 Correct 908 ms 20696 KB Output is correct
136 Correct 892 ms 20660 KB Output is correct
137 Correct 497 ms 21432 KB Output is correct
138 Correct 520 ms 21312 KB Output is correct
139 Correct 525 ms 21340 KB Output is correct
140 Correct 492 ms 21240 KB Output is correct
141 Correct 499 ms 21440 KB Output is correct
142 Correct 501 ms 21336 KB Output is correct
143 Correct 39 ms 7760 KB Output is correct
144 Correct 831 ms 21748 KB Output is correct