oj.uz

답안 #797755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797755 2023-07-29T20:56:59 Z Blagoj 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 967 ms 8396 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[200000], a[200000];
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:108:14: warning: statement has no effect [-Wunused-value]
  108 |         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 0 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 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 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 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 0 ms 340 KB Output is correct
7 Correct 295 ms 1628 KB Output is correct
8 Correct 309 ms 1888 KB Output is correct
9 Correct 335 ms 3664 KB Output is correct
10 Correct 324 ms 3668 KB Output is correct
11 Correct 288 ms 3568 KB Output is correct
12 Correct 542 ms 3684 KB Output is correct
13 Correct 301 ms 3600 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 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 0 ms 340 KB Output is correct
7 Correct 295 ms 1628 KB Output is correct
8 Correct 309 ms 1888 KB Output is correct
9 Correct 335 ms 3664 KB Output is correct
10 Correct 324 ms 3668 KB Output is correct
11 Correct 288 ms 3568 KB Output is correct
12 Correct 542 ms 3684 KB Output is correct
13 Correct 301 ms 3600 KB Output is correct
14 Correct 290 ms 2132 KB Output is correct
15 Correct 485 ms 2388 KB Output is correct
16 Correct 852 ms 3896 KB Output is correct
17 Correct 949 ms 4996 KB Output is correct
18 Correct 967 ms 5004 KB Output is correct
19 Correct 520 ms 4996 KB Output is correct
20 Correct 941 ms 4988 KB Output is correct
21 Correct 885 ms 5068 KB Output is correct
22 Correct 560 ms 4996 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 0 ms 340 KB Output is correct
7 Correct 295 ms 1628 KB Output is correct
8 Correct 309 ms 1888 KB Output is correct
9 Correct 335 ms 3664 KB Output is correct
10 Correct 324 ms 3668 KB Output is correct
11 Correct 288 ms 3568 KB Output is correct
12 Correct 542 ms 3684 KB Output is correct
13 Correct 301 ms 3600 KB Output is correct
14 Correct 290 ms 2132 KB Output is correct
15 Correct 485 ms 2388 KB Output is correct
16 Correct 852 ms 3896 KB Output is correct
17 Correct 949 ms 4996 KB Output is correct
18 Correct 967 ms 5004 KB Output is correct
19 Correct 520 ms 4996 KB Output is correct
20 Correct 941 ms 4988 KB Output is correct
21 Correct 885 ms 5068 KB Output is correct
22 Correct 560 ms 4996 KB Output is correct
23 Incorrect 51 ms 8396 KB Output isn't correct
24 Halted 0 ms 0 KB -