oj.uz

Submission #804557

# Submission time Handle Problem Language Result Execution time Memory
804557 2023-08-03T09:47:19 Z Blagoj Dancing Elephants (IOI11_elephants) C++17
100 / 100
 2500 ms 14776 KB 
#include <bits/stdc++.h>
#include "elephants.h"
 
using namespace std;
 
int n, L;
const int K = 400;
 
int block[K][2 * K], nxt[K][2 * K], val[K][2 * K], sz[K], b[(int) 2e5+5], a[(int) 2e5+5];
pair<int, int> go[K][2 * K];
 
void make(int k) {
    int r = 0;
    for (int i = 0; i < sz[k]; i++) {
        while (r < sz[k] && block[k][r] - block[k][i] <= L) r++;
        nxt[k][i] = r;
        val[k][i] = block[k][i] + L;
    }
    for (int i = sz[k] - 1; i >= 0; i--) {
        if (nxt[k][i] == sz[k]) go[k][i] = {1, val[k][i]};
        else go[k][i] = {1 + go[k][nxt[k][i]].first, go[k][nxt[k][i]].second};
    }
}
 
 
void build() {
    n = 0;
    for (int i = 0; i < K; i++)
        for (int j = 0; j < sz[i]; j++) b[n++] = block[i][j];
    for (int i = 0; i < n; i += K) {
        int r = min(n, i + K);
        sz[i / K] = r - i;
        for (int j = i; j < r; j++) block[i / K][j - i] = b[j];
        make(i / K);
    }
}
 
void init(int N, int _L, int X[]) {
    n = N, L = _L;
    for (int i = 0; i < n; i++) b[i] = a[i] = X[i];
    for (int i = 0; i < n; i += K) {
        int r = min(n, i + K);
        sz[i / K] = r - i;
        for (int j = i; j < r; j++) block[i / K][j - i] = b[j];
    }
    build();
}
 
void erase(int i, int x) {
    for (int j = 0; j < sz[i]; j++) {
        if (block[i][j] < x) continue;
        block[i][j] = block[i][j + 1];
    }
    sz[i]--;
    make(i);
}
 
void del(int x) {
    for (int i = 0; i < K; i++) {
        if (x <= block[i][sz[i] - 1]) {
            erase(i, x);
            break;
        }
    }
}
 
void add(int i, int x) {
    int dummy = x;
    for (int j = 0; j < sz[i]; j++) {
        if (block[i][j] < x) continue;
        swap(block[i][j], dummy);
    }
    block[i][sz[i]++] = dummy;
    make(i);
}
 
void Update(int x) {
    for (int i = 0; i < K; i++) {
        if (x <= block[i][sz[i] - 1]) {
            add(i, x);
            break;
        }
        if (i == (n - 1) / K) {
            add(i, x);
            break;
        }
    }
}
 
int q = 0;
 
int update(int x, int y) {
    del(a[x]);
    a[x] = y;
    Update(a[x]);
    q++;
    if (q == K) {
        build();
        q = 0;
    }
    int ans = 0, pos = block[0][0], i = 0, j = 0;
    int cnt = 0;
    while (sz[i]) {
        ans += go[i][j].first;
        pos = go[i][j].second;
        while (sz[i] && block[i][sz[i] - 1] <= pos) i++;
        if (!sz[i]) break;
        int l = 0, r = sz[i] - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (block[i][m] <= pos) l = m + 1;
            else r = m;
        }
        j = r;
    }
    return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:102:9: warning: unused variable 'cnt' [-Wunused-variable]
  102 |     int cnt = 0;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 215 ms 2472 KB Output is correct
8 Correct 239 ms 2824 KB Output is correct
9 Correct 248 ms 5020 KB Output is correct
10 Correct 262 ms 4820 KB Output is correct
11 Correct 233 ms 4740 KB Output is correct
12 Correct 437 ms 4900 KB Output is correct
13 Correct 255 ms 4604 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 215 ms 2472 KB Output is correct
8 Correct 239 ms 2824 KB Output is correct
9 Correct 248 ms 5020 KB Output is correct
10 Correct 262 ms 4820 KB Output is correct
11 Correct 233 ms 4740 KB Output is correct
12 Correct 437 ms 4900 KB Output is correct
13 Correct 255 ms 4604 KB Output is correct
14 Correct 252 ms 3556 KB Output is correct
15 Correct 393 ms 3760 KB Output is correct
16 Correct 735 ms 5508 KB Output is correct
17 Correct 750 ms 6756 KB Output is correct
18 Correct 796 ms 6688 KB Output is correct
19 Correct 374 ms 6888 KB Output is correct
20 Correct 767 ms 6756 KB Output is correct
21 Correct 718 ms 6720 KB Output is correct
22 Correct 420 ms 6320 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 215 ms 2472 KB Output is correct
8 Correct 239 ms 2824 KB Output is correct
9 Correct 248 ms 5020 KB Output is correct
10 Correct 262 ms 4820 KB Output is correct
11 Correct 233 ms 4740 KB Output is correct
12 Correct 437 ms 4900 KB Output is correct
13 Correct 255 ms 4604 KB Output is correct
14 Correct 252 ms 3556 KB Output is correct
15 Correct 393 ms 3760 KB Output is correct
16 Correct 735 ms 5508 KB Output is correct
17 Correct 750 ms 6756 KB Output is correct
18 Correct 796 ms 6688 KB Output is correct
19 Correct 374 ms 6888 KB Output is correct
20 Correct 767 ms 6756 KB Output is correct
21 Correct 718 ms 6720 KB Output is correct
22 Correct 420 ms 6320 KB Output is correct
23 Correct 1983 ms 14748 KB Output is correct
24 Correct 2157 ms 14744 KB Output is correct
25 Correct 1361 ms 14724 KB Output is correct
26 Correct 1751 ms 14776 KB Output is correct
27 Correct 1683 ms 14596 KB Output is correct
28 Correct 940 ms 5264 KB Output is correct
29 Correct 932 ms 5332 KB Output is correct
30 Correct 943 ms 5324 KB Output is correct
31 Correct 931 ms 5264 KB Output is correct
32 Correct 1297 ms 14188 KB Output is correct
33 Correct 1184 ms 13520 KB Output is correct
34 Correct 1464 ms 14396 KB Output is correct
35 Correct 950 ms 14692 KB Output is correct
36 Correct 546 ms 14164 KB Output is correct
37 Correct 1888 ms 14576 KB Output is correct
38 Correct 1476 ms 13400 KB Output is correct
39 Correct 1301 ms 14428 KB Output is correct
40 Correct 1470 ms 13428 KB Output is correct
41 Correct 2449 ms 14184 KB Output is correct
42 Correct 2500 ms 14408 KB Output is correct