oj.uz

Submission #797766

# Submission time Handle Problem Language Result Execution time Memory
797766 2023-07-29T21:22:51 Z Blagoj Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 8392 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, 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 = 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;
    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:105:9: warning: unused variable 'cnt' [-Wunused-variable]
  105 |     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 1 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 1 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 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 1 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 0 ms 340 KB Output is correct
7 Correct 296 ms 1616 KB Output is correct
8 Correct 312 ms 1888 KB Output is correct
9 Correct 338 ms 3656 KB Output is correct
10 Correct 324 ms 3668 KB Output is correct
11 Correct 287 ms 3680 KB Output is correct
12 Correct 528 ms 3664 KB Output is correct
13 Correct 312 ms 3788 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 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 0 ms 340 KB Output is correct
7 Correct 296 ms 1616 KB Output is correct
8 Correct 312 ms 1888 KB Output is correct
9 Correct 338 ms 3656 KB Output is correct
10 Correct 324 ms 3668 KB Output is correct
11 Correct 287 ms 3680 KB Output is correct
12 Correct 528 ms 3664 KB Output is correct
13 Correct 312 ms 3788 KB Output is correct
14 Correct 294 ms 2112 KB Output is correct
15 Correct 491 ms 2440 KB Output is correct
16 Correct 893 ms 3896 KB Output is correct
17 Correct 973 ms 4988 KB Output is correct
18 Correct 972 ms 4996 KB Output is correct
19 Correct 543 ms 4988 KB Output is correct
20 Correct 944 ms 4988 KB Output is correct
21 Correct 882 ms 5008 KB Output is correct
22 Correct 543 ms 4992 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 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 0 ms 340 KB Output is correct
7 Correct 296 ms 1616 KB Output is correct
8 Correct 312 ms 1888 KB Output is correct
9 Correct 338 ms 3656 KB Output is correct
10 Correct 324 ms 3668 KB Output is correct
11 Correct 287 ms 3680 KB Output is correct
12 Correct 528 ms 3664 KB Output is correct
13 Correct 312 ms 3788 KB Output is correct
14 Correct 294 ms 2112 KB Output is correct
15 Correct 491 ms 2440 KB Output is correct
16 Correct 893 ms 3896 KB Output is correct
17 Correct 973 ms 4988 KB Output is correct
18 Correct 972 ms 4996 KB Output is correct
19 Correct 543 ms 4988 KB Output is correct
20 Correct 944 ms 4988 KB Output is correct
21 Correct 882 ms 5008 KB Output is correct
22 Correct 543 ms 4992 KB Output is correct
23 Execution timed out 9065 ms 8392 KB Time limit exceeded
24 Halted 0 ms 0 KB -