oj.uz

Submission #797768

# Submission time Handle Problem Language Result Execution time Memory
797768 2023-07-29T21:25:27 Z Blagoj Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 8424 KB 
#include <bits/stdc++.h>
#include "elephants.h"

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

int n, Len;
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 i) {
    int R = 0;
    for (int L = 0; L < sz[i]; ++L) {
        while (R < sz[i] && block[i][R] - block[i][L] <= Len) ++R;
        nxt[i][L] = R;
        val[i][L] = block[i][L] + Len;
    }

    for (int j = sz[i] - 1; j >= 0; --j) {
        if (nxt[i][j] == sz[i]) {
            go[i][j] = {1, val[i][j]};
        }
        else {
            go[i][j] = {go[i][nxt[i][j]].first + 1, go[i][nxt[i][j]].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, Len = _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;
    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:110:9: warning: unused variable 'cnt' [-Wunused-variable]
  110 |     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 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 0 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 0 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 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 0 ms 340 KB Output is correct
7 Correct 293 ms 1620 KB Output is correct
8 Correct 311 ms 1888 KB Output is correct
9 Correct 336 ms 3664 KB Output is correct
10 Correct 325 ms 3664 KB Output is correct
11 Correct 288 ms 3680 KB Output is correct
12 Correct 529 ms 3664 KB Output is correct
13 Correct 307 ms 3672 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 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 0 ms 340 KB Output is correct
7 Correct 293 ms 1620 KB Output is correct
8 Correct 311 ms 1888 KB Output is correct
9 Correct 336 ms 3664 KB Output is correct
10 Correct 325 ms 3664 KB Output is correct
11 Correct 288 ms 3680 KB Output is correct
12 Correct 529 ms 3664 KB Output is correct
13 Correct 307 ms 3672 KB Output is correct
14 Correct 290 ms 2124 KB Output is correct
15 Correct 487 ms 2444 KB Output is correct
16 Correct 853 ms 3900 KB Output is correct
17 Correct 945 ms 5012 KB Output is correct
18 Correct 950 ms 5068 KB Output is correct
19 Correct 523 ms 4944 KB Output is correct
20 Correct 943 ms 5116 KB Output is correct
21 Correct 880 ms 4992 KB Output is correct
22 Correct 546 ms 4948 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 0 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 0 ms 340 KB Output is correct
7 Correct 293 ms 1620 KB Output is correct
8 Correct 311 ms 1888 KB Output is correct
9 Correct 336 ms 3664 KB Output is correct
10 Correct 325 ms 3664 KB Output is correct
11 Correct 288 ms 3680 KB Output is correct
12 Correct 529 ms 3664 KB Output is correct
13 Correct 307 ms 3672 KB Output is correct
14 Correct 290 ms 2124 KB Output is correct
15 Correct 487 ms 2444 KB Output is correct
16 Correct 853 ms 3900 KB Output is correct
17 Correct 945 ms 5012 KB Output is correct
18 Correct 950 ms 5068 KB Output is correct
19 Correct 523 ms 4944 KB Output is correct
20 Correct 943 ms 5116 KB Output is correct
21 Correct 880 ms 4992 KB Output is correct
22 Correct 546 ms 4948 KB Output is correct
23 Execution timed out 9051 ms 8424 KB Time limit exceeded
24 Halted 0 ms 0 KB -