oj.uz

답안 #826299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826299 2023-08-15T12:27:39 Z 79brue 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 312 ms 4820 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int SZ_MIN = 200, SZ_MAX = 400;

int len;

struct Group{
    int arr[SZ_MAX+2], sz; /// 0-base
    int nxt[SZ_MAX+2], cnt[SZ_MAX+2];

    void calculateNxt(){
        int last = sz;
        for(int i=sz-1; i>=0; i--){
            if(arr[sz-1] - arr[i] <= len){
                nxt[i] = i, cnt[i] = 0;
                continue;
            }
            while(arr[last-1] - arr[i] > len) last--;
            nxt[i] = nxt[last], cnt[i] = cnt[last] + 1;
        }
    }

    Group(int *A, int L, int R){
        sz = R-L+1;
        for(int i=L; i<=R; i++) arr[i-L] = A[i];
        sort(arr, arr+sz);

        calculateNxt();
    }

    void insert(int v){
        if(arr[sz-1] <= v) arr[sz++] = v;
        else for(int i=0; i<sz; i++){
            if(v <= arr[i]){
                for(int j=sz-1; j>=i; j--) arr[j+1] = arr[j];
                arr[i] = v;
                sz++;
                break;
            }
        }

        calculateNxt();
    }

    void erase(int v){
        for(int i=0; i<sz; i++){
            if(arr[i] == v){
                for(int j=i+1; j<sz; j++) arr[j-1] = arr[j];
                arr[--sz] = 0;
                break;
            }
            if(i==sz-1) exit(1);
        }

        if(sz) calculateNxt();
    }
};

int n, k;
int arr[150002];
Group *groups[1002]; /// 0-base

void init(int N, int L, int X[]){
    n = N;
    len = L;
    for(int i=0; i<n; i++) arr[i] = X[i];
    for(int s=0; s<n; s++){
        int e = min(s+SZ_MIN-1, n-1);
        groups[k++] = new Group(arr, s, e);
        s = e;
    }
}

int update(int I, int y){
    /// 제거
    for(int i=0; i<k; i++){
        if(groups[i]->arr[0] <= arr[I] && arr[I] <= groups[i]->arr[groups[i]->sz-1]){
            groups[i]->erase(arr[I]);
            if(groups[i]->sz == 0){
                for(int j=i+1; j<k; j++) groups[j-1] = groups[j];
                --k;
                groups[k] = nullptr;
            }
            break;
        }
    }
    arr[I] = y;
    /// 삽입
    if(k==0){
        ++k;
        int X[1] = {y};
        groups[0] = new Group(X, 0, 0);
    }
    else{
        for(int i=0; i<k; i++){
            if(groups[i]->arr[groups[i]->sz-1] >= y || i==k-1){
                groups[i]->insert(y);
                if(groups[i]->sz >= SZ_MAX){
                    int X[SZ_MAX+2], len = groups[i]->sz;
                    for(int j=0; j<groups[i]->sz; j++) X[j] = groups[i]->arr[j];
                    for(int j=k-1; j>=i+1; j--) groups[j+1] = groups[j];
                    k++;
                    groups[i] = new Group(X, 0, SZ_MIN-1);
                    groups[i+1] = new Group(X, SZ_MIN, len-1);
                }
                break;
            }
        }
    }

    /// 계산
    int lastX = -2e9, c=0;
    for(int i=0; i<k; i++){
        if(groups[i]->arr[groups[i]->sz-1] - lastX <= len) continue;
        int x = upper_bound(groups[i]->arr, groups[i]->arr + groups[i]->sz, lastX + len) - groups[i]->arr;
        lastX = groups[i]->arr[groups[i]->nxt[x]];
        c += 1 + groups[i]->cnt[x];
    }

    return c;
}

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 0 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 0 ms 340 KB Output is correct
4 Correct 0 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 0 ms 340 KB Output is correct
4 Correct 0 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 115 ms 3604 KB Output is correct
8 Correct 138 ms 3700 KB Output is correct
9 Correct 229 ms 2496 KB Output is correct
10 Correct 198 ms 4764 KB Output is correct
11 Correct 159 ms 4820 KB Output is correct
12 Correct 312 ms 3432 KB Output is correct
13 Correct 211 ms 4804 KB Output is correct

Subtask #4
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 0 ms 340 KB Output is correct
4 Correct 0 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 115 ms 3604 KB Output is correct
8 Correct 138 ms 3700 KB Output is correct
9 Correct 229 ms 2496 KB Output is correct
10 Correct 198 ms 4764 KB Output is correct
11 Correct 159 ms 4820 KB Output is correct
12 Correct 312 ms 3432 KB Output is correct
13 Correct 211 ms 4804 KB Output is correct
14 Incorrect 96 ms 3952 KB Output isn't correct
15 Halted 0 ms 0 KB -

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 0 ms 340 KB Output is correct
4 Correct 0 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 115 ms 3604 KB Output is correct
8 Correct 138 ms 3700 KB Output is correct
9 Correct 229 ms 2496 KB Output is correct
10 Correct 198 ms 4764 KB Output is correct
11 Correct 159 ms 4820 KB Output is correct
12 Correct 312 ms 3432 KB Output is correct
13 Correct 211 ms 4804 KB Output is correct
14 Incorrect 96 ms 3952 KB Output isn't correct
15 Halted 0 ms 0 KB -