oj.uz

Submission #797748

# Submission time Handle Problem Language Result Execution time Memory
797748 2023-07-29T20:46:33 Z Blagoj Dancing Elephants (IOI11_elephants) C++17
97 / 100
 889 ms 13388 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[150005], a[150005];
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 = 0; j < r; j++) block[i / K][j] = b[i + 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 = 0; j < r; j++) block[i / K][j] = b[i + 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;
    while (sz[i]) {
        ans += go[i][j].first;
        pos = go[i][j].second;
        for (i; 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:104:14: warning: statement has no effect [-Wunused-value]
  104 |         for (i; sz[i] && block[i][sz[i] - 1] <= pos; i++) {
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 0 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 1604 KB Output is correct
8 Correct 233 ms 2908 KB Output is correct
9 Correct 281 ms 5220 KB Output is correct
10 Correct 290 ms 5012 KB Output is correct
11 Correct 285 ms 4944 KB Output is correct
12 Correct 472 ms 5100 KB Output is correct
13 Correct 283 ms 4692 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 1 ms 340 KB Output is correct
3 Correct 0 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 1604 KB Output is correct
8 Correct 233 ms 2908 KB Output is correct
9 Correct 281 ms 5220 KB Output is correct
10 Correct 290 ms 5012 KB Output is correct
11 Correct 285 ms 4944 KB Output is correct
12 Correct 472 ms 5100 KB Output is correct
13 Correct 283 ms 4692 KB Output is correct
14 Correct 260 ms 3632 KB Output is correct
15 Correct 372 ms 3860 KB Output is correct
16 Correct 776 ms 5708 KB Output is correct
17 Correct 841 ms 7040 KB Output is correct
18 Correct 889 ms 6964 KB Output is correct
19 Correct 465 ms 7116 KB Output is correct
20 Correct 832 ms 7032 KB Output is correct
21 Correct 801 ms 7084 KB Output is correct
22 Correct 505 ms 6604 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 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 1604 KB Output is correct
8 Correct 233 ms 2908 KB Output is correct
9 Correct 281 ms 5220 KB Output is correct
10 Correct 290 ms 5012 KB Output is correct
11 Correct 285 ms 4944 KB Output is correct
12 Correct 472 ms 5100 KB Output is correct
13 Correct 283 ms 4692 KB Output is correct
14 Correct 260 ms 3632 KB Output is correct
15 Correct 372 ms 3860 KB Output is correct
16 Correct 776 ms 5708 KB Output is correct
17 Correct 841 ms 7040 KB Output is correct
18 Correct 889 ms 6964 KB Output is correct
19 Correct 465 ms 7116 KB Output is correct
20 Correct 832 ms 7032 KB Output is correct
21 Correct 801 ms 7084 KB Output is correct
22 Correct 505 ms 6604 KB Output is correct
23 Incorrect 54 ms 13388 KB Output isn't correct
24 Halted 0 ms 0 KB -