oj.uz

Submission #1042525

# Submission time Handle Problem Language Result Execution time Memory
1042525 2024-08-03T06:17:41 Z sleepntsheep Inside information (BOI21_servers) C
52.5 / 100
 3500 ms 170384 KB 
#include <stdio.h>
#include <stdlib.h>

int max(int i, int j) { return i > j ? i : j; }
/*
 * Try merge small 2 large, with persistent ds -> O(nlg^2n)
 * How to maintain "frequency" of each data chunk ? ?? 
 *
 */

#define N 120001
#define B 100
#define M 30000000

int n, q, L[M], R[M], A[M], alc, root[N], temp, freq[N];
int p2(int l, int r, int x) {
  int p = ++alc;
  A[p] = A[L[p]=l] + A[R[p]=r] + x;
  return p;
}
int pbuild(int l, int r) {
  return l == r ? ++alc : p2(pbuild(l, (l+r)/2), pbuild((l+r)/2+1, r), 0);
}
int pupd(int v, int l, int r, int p) {
  if (l == r) {
    if(!A[v])++freq[p];
    return p2(0, 0, 1);
  }
  if (p <= (l+r)/2) return p2(pupd(L[v], l, (l+r)/2, p), R[v], 0);
  return p2(L[v], pupd(R[v], (l+r)/2+1, r, p), 0);
}
int pqry(int v, int l, int r, int k) {
  if (l == r) return l;
  if (A[L[v]] < k) return pqry(R[v], (l+r)/2+1, r, k - A[L[v]]);
  return pqry(L[v], l, (l+r)/2, k);
}
int ppt(int v, int l, int r, int p) {
  if (l == r) return A[v];
  return p <= (l+r)/2 ? ppt(L[v], l, (l+r)/2, p) : ppt(R[v], (l+r)/2+1, r, p);
}

int main() {
  scanf("%d%d", &n, &q);

  root[0] = pbuild(1, n);
  for (int i = 1; i <= n; ++i)
    root[i] = pupd(root[0], 1, n, i);

  q = n + q - 1;
  for (int j = 0, i = 0; i < q; ++i) {
    char type[2];
    int a, b;
    scanf(" %s%d", type, &a);
    if ('S' == type[0]) {
      scanf("%d", &b);
      if (A[root[a]] > A[root[b]])
        temp = a, a = b, b = temp;
      int tot = A[root[a]], at = 0;
      while (at < tot) {
        int p = pqry(root[a], 1, n, ++at);
        --freq[p];
        root[b] = pupd(root[b], 1, n, p);
      }
      root[a] = root[b];
      /* delete freq in a, need to count all elem in b twice(since duplicated)
       * how??*/
    } else if ('Q' == type[0]) {
      scanf("%d", &b);
      puts(ppt(root[a], 1, n, b) ? "yes" : "no");
    } else {
      int z=0;for(int i=1;i<=n;++i)z+=ppt(root[i],1,n,a);
      printf("%d\n", z);
    }
  }
}

Compilation message

servers.c: In function 'main':
servers.c:51:12: warning: unused variable 'j' [-Wunused-variable]
   51 |   for (int j = 0, i = 0; i < q; ++i) {
      |            ^
servers.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d", &n, &q);
      |   ^~~~~~~~~~~~~~~~~~~~~
servers.c:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf(" %s%d", type, &a);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
servers.c:56:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~
servers.c:69:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2648 KB Output is correct
2 Correct 24 ms 3740 KB Output is correct
3 Correct 27 ms 2456 KB Output is correct
4 Correct 27 ms 2404 KB Output is correct
5 Correct 25 ms 2392 KB Output is correct
6 Correct 27 ms 2152 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2648 KB Output is correct
2 Correct 24 ms 3740 KB Output is correct
3 Correct 27 ms 2456 KB Output is correct
4 Correct 27 ms 2404 KB Output is correct
5 Correct 25 ms 2392 KB Output is correct
6 Correct 27 ms 2152 KB Output is correct
7 Correct 18 ms 604 KB Output is correct
8 Correct 3150 ms 2396 KB Output is correct
9 Correct 3400 ms 2496 KB Output is correct
10 Correct 3243 ms 2212 KB Output is correct
11 Correct 2979 ms 2128 KB Output is correct
12 Correct 2877 ms 2148 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 211 ms 54944 KB Output is correct
3 Correct 190 ms 54896 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 211 ms 54944 KB Output is correct
3 Correct 190 ms 54896 KB Output is correct
4 Correct 17 ms 600 KB Output is correct
5 Execution timed out 3577 ms 31012 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 185 ms 64828 KB Output is correct
3 Correct 167 ms 64656 KB Output is correct
4 Correct 107 ms 55892 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 185 ms 64828 KB Output is correct
3 Correct 167 ms 64656 KB Output is correct
4 Correct 107 ms 55892 KB Output is correct
5 Correct 18 ms 2904 KB Output is correct
6 Execution timed out 3597 ms 29980 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 604 KB Output is correct
2 Correct 256 ms 144468 KB Output is correct
3 Correct 245 ms 67528 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 604 KB Output is correct
2 Correct 256 ms 144468 KB Output is correct
3 Correct 245 ms 67528 KB Output is correct
4 Correct 22 ms 2648 KB Output is correct
5 Execution timed out 3555 ms 30704 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 188 ms 64716 KB Output is correct
3 Correct 187 ms 64848 KB Output is correct
4 Correct 111 ms 55632 KB Output is correct
5 Correct 17 ms 648 KB Output is correct
6 Correct 236 ms 144576 KB Output is correct
7 Correct 213 ms 67536 KB Output is correct
8 Correct 240 ms 68436 KB Output is correct
9 Correct 238 ms 68176 KB Output is correct
10 Correct 250 ms 76960 KB Output is correct
11 Correct 267 ms 78676 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 188 ms 64716 KB Output is correct
3 Correct 187 ms 64848 KB Output is correct
4 Correct 111 ms 55632 KB Output is correct
5 Correct 17 ms 648 KB Output is correct
6 Correct 236 ms 144576 KB Output is correct
7 Correct 213 ms 67536 KB Output is correct
8 Correct 240 ms 68436 KB Output is correct
9 Correct 238 ms 68176 KB Output is correct
10 Correct 250 ms 76960 KB Output is correct
11 Correct 267 ms 78676 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Execution timed out 3567 ms 29972 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 600 KB Output is correct
2 Correct 27 ms 2396 KB Output is correct
3 Correct 27 ms 3968 KB Output is correct
4 Correct 26 ms 2384 KB Output is correct
5 Correct 26 ms 2276 KB Output is correct
6 Correct 28 ms 2132 KB Output is correct
7 Correct 16 ms 604 KB Output is correct
8 Correct 202 ms 55012 KB Output is correct
9 Correct 194 ms 55692 KB Output is correct
10 Correct 17 ms 2648 KB Output is correct
11 Correct 182 ms 64852 KB Output is correct
12 Correct 181 ms 64848 KB Output is correct
13 Correct 144 ms 55384 KB Output is correct
14 Correct 16 ms 604 KB Output is correct
15 Correct 245 ms 144572 KB Output is correct
16 Correct 211 ms 67412 KB Output is correct
17 Correct 235 ms 68284 KB Output is correct
18 Correct 224 ms 68180 KB Output is correct
19 Correct 254 ms 77140 KB Output is correct
20 Correct 277 ms 78672 KB Output is correct
21 Correct 211 ms 58964 KB Output is correct
22 Correct 231 ms 66856 KB Output is correct
23 Correct 258 ms 71252 KB Output is correct
24 Correct 255 ms 71204 KB Output is correct
25 Correct 199 ms 60492 KB Output is correct
26 Correct 411 ms 160184 KB Output is correct
27 Correct 412 ms 170384 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 600 KB Output is correct
2 Correct 27 ms 2396 KB Output is correct
3 Correct 27 ms 3968 KB Output is correct
4 Correct 26 ms 2384 KB Output is correct
5 Correct 26 ms 2276 KB Output is correct
6 Correct 28 ms 2132 KB Output is correct
7 Correct 16 ms 604 KB Output is correct
8 Correct 202 ms 55012 KB Output is correct
9 Correct 194 ms 55692 KB Output is correct
10 Correct 17 ms 2648 KB Output is correct
11 Correct 182 ms 64852 KB Output is correct
12 Correct 181 ms 64848 KB Output is correct
13 Correct 144 ms 55384 KB Output is correct
14 Correct 16 ms 604 KB Output is correct
15 Correct 245 ms 144572 KB Output is correct
16 Correct 211 ms 67412 KB Output is correct
17 Correct 235 ms 68284 KB Output is correct
18 Correct 224 ms 68180 KB Output is correct
19 Correct 254 ms 77140 KB Output is correct
20 Correct 277 ms 78672 KB Output is correct
21 Correct 211 ms 58964 KB Output is correct
22 Correct 231 ms 66856 KB Output is correct
23 Correct 258 ms 71252 KB Output is correct
24 Correct 255 ms 71204 KB Output is correct
25 Correct 199 ms 60492 KB Output is correct
26 Correct 411 ms 160184 KB Output is correct
27 Correct 412 ms 170384 KB Output is correct
28 Correct 18 ms 2652 KB Output is correct
29 Correct 3202 ms 2200 KB Output is correct
30 Correct 3438 ms 2452 KB Output is correct
31 Correct 3252 ms 2168 KB Output is correct
32 Correct 2964 ms 2132 KB Output is correct
33 Correct 2883 ms 3696 KB Output is correct
34 Correct 17 ms 600 KB Output is correct
35 Execution timed out 3543 ms 32556 KB Time limit exceeded
36 Halted 0 ms 0 KB -