oj.uz

답안 #797751

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797751 2023-07-29T20:53:53 Z Blagoj 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 13468 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[250005], a[250005];
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 216 ms 1624 KB Output is correct
8 Correct 246 ms 1892 KB Output is correct
9 Correct 314 ms 3668 KB Output is correct
10 Correct 294 ms 3680 KB Output is correct
11 Correct 267 ms 3672 KB Output is correct
12 Correct 483 ms 3676 KB Output is correct
13 Correct 302 ms 3668 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 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 216 ms 1624 KB Output is correct
8 Correct 246 ms 1892 KB Output is correct
9 Correct 314 ms 3668 KB Output is correct
10 Correct 294 ms 3680 KB Output is correct
11 Correct 267 ms 3672 KB Output is correct
12 Correct 483 ms 3676 KB Output is correct
13 Correct 302 ms 3668 KB Output is correct
14 Correct 282 ms 3624 KB Output is correct
15 Correct 389 ms 3872 KB Output is correct
16 Correct 793 ms 5708 KB Output is correct
17 Correct 864 ms 7032 KB Output is correct
18 Correct 928 ms 6956 KB Output is correct
19 Correct 489 ms 7152 KB Output is correct
20 Correct 867 ms 7024 KB Output is correct
21 Correct 800 ms 6988 KB Output is correct
22 Correct 509 ms 6592 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 216 ms 1624 KB Output is correct
8 Correct 246 ms 1892 KB Output is correct
9 Correct 314 ms 3668 KB Output is correct
10 Correct 294 ms 3680 KB Output is correct
11 Correct 267 ms 3672 KB Output is correct
12 Correct 483 ms 3676 KB Output is correct
13 Correct 302 ms 3668 KB Output is correct
14 Correct 282 ms 3624 KB Output is correct
15 Correct 389 ms 3872 KB Output is correct
16 Correct 793 ms 5708 KB Output is correct
17 Correct 864 ms 7032 KB Output is correct
18 Correct 928 ms 6956 KB Output is correct
19 Correct 489 ms 7152 KB Output is correct
20 Correct 867 ms 7024 KB Output is correct
21 Correct 800 ms 6988 KB Output is correct
22 Correct 509 ms 6592 KB Output is correct
23 Execution timed out 9056 ms 13468 KB Time limit exceeded
24 Halted 0 ms 0 KB -