oj.uz

Submission #1031151

# Submission time Handle Problem Language Result Execution time Memory
1031151 2024-07-22T15:35:06 Z sleepntsheep Tourism (JOI23_tourism) C
100 / 100
 1033 ms 43064 KB 
#include <stdio.h>
#include <stdlib.h>

int *mem(int i) { return (int *)calloc(i, sizeof(int)); }
int *remem(int *e, int i) { return (int*)realloc(e, sizeof(int) * i); }
void pus_(int **eh, int *eo, int x) {
  int o = eo[0]++;
  if (o == 0)
    eh[0] = mem(2);
  else if ((o & (o - 1)) == 0)
    eh[0] = remem(eh[0], 2 * o);
  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 1000000
#define NN 1000000
#define MM 1000000
#define NN_ 1000005
/*BEGINfenwick*/
int fw[NN_];
void upd(int p, int k) {
  for (; p < NN_; p |= p + 1)
    fw[p] += k;
}
long long qry(int p) {
  if (p >= NN_)
    p = NN_;
  long long z = 0;
  for (++p; p > 0; p &= p - 1)
    z += fw[p - 1];
  return z;
}
/*ENDfenwick*/

int tout[NN], Ans[QQ], N, M, Q, C[MM], L[QQ], R[QQ], X[NN], Y[NN], Freq[NN],
    *Occ[NN]; /* Freq[u] = how many k such that C[k] = u , Occ[u] = that list of
                 ks */

/* BEGINoriginal tree*/
int *adj[NN], deg[NN], dfn[NN], timer,
    /*for lca, lca for virtual tree*/ 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;
}
/* END original tree*/
/*BEGIN virtual tree */
int *vtadj[NN], *vtw[NN], vtdeg[NN], vtdeg2[NN];
void virtual_link(int u, int v, int w) {
    pus(vtadj[u], vtdeg[u], v);
    pus(vtw[u], vtdeg2[u], w);
}
void virtual_link_bi(int u, int v, int w) { virtual_link(u, v, w), virtual_link(v, u, w); }
/*END virtualt ree*/

/* compare nodes by dfn time */
int Compar_Dfn(const void *i, const void *j) {
  return dfn[*(const int *)i] - dfn[*(const int *)j];
}

/* in virtual tree, lef[u] stores highest k < m such that C[k] == u,
 *              analogously, rgt[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 lef[NN], rgt[NN];
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])
    rgt[u] = Occ[u][ub];
  if ((ub && Occ[u][--ub] < m) || (ub && Occ[u][--ub] < m))
      lef[u] = Occ[u][ub];

  //printf(" At %d, LR = %d %d\n",u,lef[u],rgt[u]);
  for (int j = 0; j < vtdeg[u]; ++j)
    if (vtadj[u][j] != p) {
      vtdfs(vtadj[u][j], u, vtw[u][j], m);
      lef[u] = max(lef[u], lef[vtadj[u][j]]);
      rgt[u] = min(rgt[u], rgt[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 lef[*(const int*)b] - lef[*(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;
/* store active query for dnc, that is query i which L[i] <= m <= R[i] */
void dnc(
    int l, int r, int *candidates,
    int count_candidates) { /*  calc answer for alll queries containing m */
  if (l >= r) {
      //free(candidates);
    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]]=0;
      vtdeg[V[i]] = vtdeg2[V[i]] = 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 lef and rgt */
  for (int i = 0; i < ord; ++i)
    lef[V[i]] = -2, rgt[V[i]] = 1e9 + 2;

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

  //printf(" HERE ! %d %d\n", l, r); printf(" Current |V| = %d\n", ord); printf("  : ");for(int i=0;i<ord;++i)printf(" %d : L = %d, R = %d\n", V[i],lef[V[i]],rgt[V[i]]);puts("");


  /* collect all active queries, one that contain m (ql <= m <= qr) */
  int *active = NULL, nactive = 0,
      *left = NULL, nleft = NULL,
      *right = 0, 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(left, nleft, j);
    else if (L[j] > m)
      pus(right, nright, j);
  }
  free(candidates);

  //printf (" Active queries (%d): ",nactive); for (int i=0;i<nactive;++i)printf("%d ",active[i]);puts("");

  /* do fenwick to get answers */
  /* for each node that is not C[m], the edge about it has (x, y, w)
   * add w to each active querys, except ones that x < ql and qr < y
   * by adding 1 to x, -1 to y
   * that is add -w to the one that [x, y]  cover [ql,qr]
   * this can be done with sweepline (wtf)
   *
   * have a sum fenwick tree
   * sort those (x, y, w) edges by increasing x [C2]
   * also sort active querys by increasing ql [C3]
   * do two pointer, and on edges, update -w to y,
   * on queries, add sumfenwick(qr, N) to Ans[query]
   */

  /* nah ignore the above comment 
   *
   * 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 && lef[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 && lef[V[pi]] < L[qi])
          upd(rgt[V[pi]], vt_up[V[pi]]), ++pi;
      Ans[qi] += qry(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 && lef[V[pi]] < L[qi])
          upd(rgt[V[pi]], -vt_up[V[pi]]), ++pi;
  }

  //free(V);
  //free(active);

  /* continue dnc */
  /* left = queries i in active such that R[i] < m,
   * right = queries i in active such that L[i] > m; */
  dnc(l, m, left, nleft);
  dnc(m + 1, r, right, nright);
  /* dont need to free left and right, since dnc() owns pointers */
}

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);
  dep[0] = 0, jmp[0] = par[0] = 0;
  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 = mem(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);
}

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

Compilation message

tourism.c: In function 'dnc':
tourism.c:206:29: warning: initialization of 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
  206 |       *left = NULL, nleft = NULL,
      |                             ^~~~
tourism.c: In function 'main':
tourism.c:287:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:289:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  289 |     scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:293:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  293 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:296:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  296 |     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 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 680 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 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 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 2 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 688 KB Output is correct
20 Correct 1 ms 600 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 716 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 600 KB Output is correct
27 Correct 0 ms 604 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 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 680 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 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 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 2 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 688 KB Output is correct
20 Correct 1 ms 600 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 716 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 600 KB Output is correct
27 Correct 0 ms 604 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 1116 KB Output is correct
31 Correct 7 ms 1116 KB Output is correct
32 Correct 10 ms 1116 KB Output is correct
33 Correct 9 ms 1128 KB Output is correct
34 Correct 9 ms 1116 KB Output is correct
35 Correct 8 ms 1116 KB Output is correct
36 Correct 9 ms 1160 KB Output is correct
37 Correct 8 ms 1240 KB Output is correct
38 Correct 7 ms 1112 KB Output is correct
39 Correct 7 ms 1116 KB Output is correct
40 Correct 7 ms 1296 KB Output is correct
41 Correct 6 ms 1116 KB Output is correct
42 Correct 6 ms 1116 KB Output is correct
43 Correct 6 ms 1312 KB Output is correct
44 Correct 8 ms 1084 KB Output is correct
45 Correct 8 ms 1212 KB Output is correct
46 Correct 12 ms 1312 KB Output is correct
47 Correct 7 ms 1112 KB Output is correct
48 Correct 7 ms 1088 KB Output is correct
49 Correct 7 ms 1116 KB Output is correct
50 Correct 6 ms 1116 KB Output is correct
51 Correct 6 ms 1208 KB Output is correct
52 Correct 6 ms 1116 KB Output is correct
53 Correct 6 ms 1112 KB Output is correct
54 Correct 6 ms 1240 KB Output is correct
55 Correct 6 ms 1132 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 2 ms 604 KB Output is correct
58 Correct 9 ms 1116 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 451 ms 28280 KB Output is correct
5 Correct 331 ms 27564 KB Output is correct
6 Correct 437 ms 34980 KB Output is correct
7 Correct 567 ms 40160 KB Output is correct
8 Correct 588 ms 40140 KB Output is correct
9 Correct 609 ms 40204 KB Output is correct
10 Correct 601 ms 39892 KB Output is correct
11 Correct 566 ms 40176 KB Output is correct
12 Correct 271 ms 38216 KB Output is correct
13 Correct 312 ms 38288 KB Output is correct
14 Correct 304 ms 38220 KB Output is correct
15 Correct 42 ms 15952 KB Output is correct
16 Correct 607 ms 41488 KB Output is correct
17 Correct 52 ms 7628 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 419 ms 19824 KB Output is correct
3 Correct 706 ms 28980 KB Output is correct
4 Correct 552 ms 23344 KB Output is correct
5 Correct 835 ms 37308 KB Output is correct
6 Correct 848 ms 37564 KB Output is correct
7 Correct 824 ms 37812 KB Output is correct
8 Correct 837 ms 37640 KB Output is correct
9 Correct 861 ms 37460 KB Output is correct
10 Correct 823 ms 37568 KB Output is correct
11 Correct 917 ms 37712 KB Output is correct
12 Correct 896 ms 37772 KB Output is correct
13 Correct 836 ms 38232 KB Output is correct
14 Correct 888 ms 39356 KB Output is correct
15 Correct 901 ms 43064 KB Output is correct
16 Correct 819 ms 38224 KB Output is correct
17 Correct 854 ms 38028 KB Output is correct
18 Correct 827 ms 37820 KB Output is correct
19 Correct 911 ms 35008 KB Output is correct
20 Correct 893 ms 34908 KB Output is correct
21 Correct 907 ms 35036 KB Output is correct
22 Correct 926 ms 35348 KB Output is correct
23 Correct 886 ms 34796 KB Output is correct
24 Correct 884 ms 35028 KB Output is correct
25 Correct 896 ms 34940 KB Output is correct
26 Correct 916 ms 34940 KB Output is correct
27 Correct 981 ms 34936 KB Output is correct
28 Correct 934 ms 34908 KB Output is correct
29 Correct 952 ms 35160 KB Output is correct
30 Correct 953 ms 35420 KB Output is correct
31 Correct 962 ms 35612 KB Output is correct
32 Correct 1006 ms 36656 KB Output is correct
33 Correct 1033 ms 38168 KB Output is correct
34 Correct 1008 ms 40852 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 709 ms 32012 KB Output is correct
5 Correct 728 ms 32968 KB Output is correct
6 Correct 825 ms 38484 KB Output is correct
7 Correct 855 ms 41504 KB Output is correct
8 Correct 852 ms 41388 KB Output is correct
9 Correct 872 ms 41504 KB Output is correct
10 Correct 881 ms 41476 KB Output is correct
11 Correct 878 ms 41400 KB Output is correct
12 Correct 853 ms 41536 KB Output is correct
13 Correct 864 ms 41556 KB Output is correct
14 Correct 49 ms 7628 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 680 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 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 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 2 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 688 KB Output is correct
20 Correct 1 ms 600 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 716 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 600 KB Output is correct
27 Correct 0 ms 604 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 1116 KB Output is correct
31 Correct 7 ms 1116 KB Output is correct
32 Correct 10 ms 1116 KB Output is correct
33 Correct 9 ms 1128 KB Output is correct
34 Correct 9 ms 1116 KB Output is correct
35 Correct 8 ms 1116 KB Output is correct
36 Correct 9 ms 1160 KB Output is correct
37 Correct 8 ms 1240 KB Output is correct
38 Correct 7 ms 1112 KB Output is correct
39 Correct 7 ms 1116 KB Output is correct
40 Correct 7 ms 1296 KB Output is correct
41 Correct 6 ms 1116 KB Output is correct
42 Correct 6 ms 1116 KB Output is correct
43 Correct 6 ms 1312 KB Output is correct
44 Correct 8 ms 1084 KB Output is correct
45 Correct 8 ms 1212 KB Output is correct
46 Correct 12 ms 1312 KB Output is correct
47 Correct 7 ms 1112 KB Output is correct
48 Correct 7 ms 1088 KB Output is correct
49 Correct 7 ms 1116 KB Output is correct
50 Correct 6 ms 1116 KB Output is correct
51 Correct 6 ms 1208 KB Output is correct
52 Correct 6 ms 1116 KB Output is correct
53 Correct 6 ms 1112 KB Output is correct
54 Correct 6 ms 1240 KB Output is correct
55 Correct 6 ms 1132 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 2 ms 604 KB Output is correct
58 Correct 9 ms 1116 KB Output is correct
59 Correct 0 ms 604 KB Output is correct
60 Correct 1 ms 604 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 451 ms 28280 KB Output is correct
63 Correct 331 ms 27564 KB Output is correct
64 Correct 437 ms 34980 KB Output is correct
65 Correct 567 ms 40160 KB Output is correct
66 Correct 588 ms 40140 KB Output is correct
67 Correct 609 ms 40204 KB Output is correct
68 Correct 601 ms 39892 KB Output is correct
69 Correct 566 ms 40176 KB Output is correct
70 Correct 271 ms 38216 KB Output is correct
71 Correct 312 ms 38288 KB Output is correct
72 Correct 304 ms 38220 KB Output is correct
73 Correct 42 ms 15952 KB Output is correct
74 Correct 607 ms 41488 KB Output is correct
75 Correct 52 ms 7628 KB Output is correct
76 Correct 1 ms 604 KB Output is correct
77 Correct 419 ms 19824 KB Output is correct
78 Correct 706 ms 28980 KB Output is correct
79 Correct 552 ms 23344 KB Output is correct
80 Correct 835 ms 37308 KB Output is correct
81 Correct 848 ms 37564 KB Output is correct
82 Correct 824 ms 37812 KB Output is correct
83 Correct 837 ms 37640 KB Output is correct
84 Correct 861 ms 37460 KB Output is correct
85 Correct 823 ms 37568 KB Output is correct
86 Correct 917 ms 37712 KB Output is correct
87 Correct 896 ms 37772 KB Output is correct
88 Correct 836 ms 38232 KB Output is correct
89 Correct 888 ms 39356 KB Output is correct
90 Correct 901 ms 43064 KB Output is correct
91 Correct 819 ms 38224 KB Output is correct
92 Correct 854 ms 38028 KB Output is correct
93 Correct 827 ms 37820 KB Output is correct
94 Correct 911 ms 35008 KB Output is correct
95 Correct 893 ms 34908 KB Output is correct
96 Correct 907 ms 35036 KB Output is correct
97 Correct 926 ms 35348 KB Output is correct
98 Correct 886 ms 34796 KB Output is correct
99 Correct 884 ms 35028 KB Output is correct
100 Correct 896 ms 34940 KB Output is correct
101 Correct 916 ms 34940 KB Output is correct
102 Correct 981 ms 34936 KB Output is correct
103 Correct 934 ms 34908 KB Output is correct
104 Correct 952 ms 35160 KB Output is correct
105 Correct 953 ms 35420 KB Output is correct
106 Correct 962 ms 35612 KB Output is correct
107 Correct 1006 ms 36656 KB Output is correct
108 Correct 1033 ms 38168 KB Output is correct
109 Correct 1008 ms 40852 KB Output is correct
110 Correct 1 ms 604 KB Output is correct
111 Correct 0 ms 604 KB Output is correct
112 Correct 1 ms 604 KB Output is correct
113 Correct 709 ms 32012 KB Output is correct
114 Correct 728 ms 32968 KB Output is correct
115 Correct 825 ms 38484 KB Output is correct
116 Correct 855 ms 41504 KB Output is correct
117 Correct 852 ms 41388 KB Output is correct
118 Correct 872 ms 41504 KB Output is correct
119 Correct 881 ms 41476 KB Output is correct
120 Correct 878 ms 41400 KB Output is correct
121 Correct 853 ms 41536 KB Output is correct
122 Correct 864 ms 41556 KB Output is correct
123 Correct 49 ms 7628 KB Output is correct
124 Correct 751 ms 36444 KB Output is correct
125 Correct 585 ms 29756 KB Output is correct
126 Correct 911 ms 40808 KB Output is correct
127 Correct 988 ms 40760 KB Output is correct
128 Correct 925 ms 41012 KB Output is correct
129 Correct 912 ms 40876 KB Output is correct
130 Correct 904 ms 41012 KB Output is correct
131 Correct 774 ms 39064 KB Output is correct
132 Correct 728 ms 39992 KB Output is correct
133 Correct 769 ms 37516 KB Output is correct
134 Correct 1002 ms 38316 KB Output is correct
135 Correct 1000 ms 38640 KB Output is correct
136 Correct 983 ms 38800 KB Output is correct
137 Correct 561 ms 34152 KB Output is correct
138 Correct 618 ms 34208 KB Output is correct
139 Correct 577 ms 34020 KB Output is correct
140 Correct 555 ms 33964 KB Output is correct
141 Correct 601 ms 33952 KB Output is correct
142 Correct 580 ms 33952 KB Output is correct
143 Correct 35 ms 9812 KB Output is correct
144 Correct 944 ms 42088 KB Output is correct