oj.uz

답안 #797770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797770 2023-07-29T21:26:48 Z Blagoj 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 861 ms 9676 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 l = 0; l < n; l += K) {
        int r = min(l + K, n);
        sz[l / K] = r - l;
        for (int i = l; i < r; i++) block[l / K][i - l] = b[i];
        int i = l / K;
        make(i);
    }
}

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:106:9: warning: unused variable 'cnt' [-Wunused-variable]
  106 |     int cnt = 0;
      |         ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
5 Correct 0 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 0 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 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 293 ms 1612 KB Output is correct
8 Correct 308 ms 1912 KB Output is correct
9 Correct 299 ms 3656 KB Output is correct
10 Correct 297 ms 3680 KB Output is correct
11 Correct 256 ms 3668 KB Output is correct
12 Correct 500 ms 3672 KB Output is correct
13 Correct 262 ms 3668 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 293 ms 1612 KB Output is correct
8 Correct 308 ms 1912 KB Output is correct
9 Correct 299 ms 3656 KB Output is correct
10 Correct 297 ms 3680 KB Output is correct
11 Correct 256 ms 3668 KB Output is correct
12 Correct 500 ms 3672 KB Output is correct
13 Correct 262 ms 3668 KB Output is correct
14 Correct 286 ms 2120 KB Output is correct
15 Correct 472 ms 2440 KB Output is correct
16 Correct 805 ms 3896 KB Output is correct
17 Correct 859 ms 4988 KB Output is correct
18 Correct 861 ms 5068 KB Output is correct
19 Correct 432 ms 4988 KB Output is correct
20 Correct 848 ms 4984 KB Output is correct
21 Correct 802 ms 5068 KB Output is correct
22 Correct 429 ms 4992 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 293 ms 1612 KB Output is correct
8 Correct 308 ms 1912 KB Output is correct
9 Correct 299 ms 3656 KB Output is correct
10 Correct 297 ms 3680 KB Output is correct
11 Correct 256 ms 3668 KB Output is correct
12 Correct 500 ms 3672 KB Output is correct
13 Correct 262 ms 3668 KB Output is correct
14 Correct 286 ms 2120 KB Output is correct
15 Correct 472 ms 2440 KB Output is correct
16 Correct 805 ms 3896 KB Output is correct
17 Correct 859 ms 4988 KB Output is correct
18 Correct 861 ms 5068 KB Output is correct
19 Correct 432 ms 4988 KB Output is correct
20 Correct 848 ms 4984 KB Output is correct
21 Correct 802 ms 5068 KB Output is correct
22 Correct 429 ms 4992 KB Output is correct
23 Incorrect 52 ms 9676 KB Output isn't correct
24 Halted 0 ms 0 KB -