oj.uz

Submission #826285

# Submission time Handle Problem Language Result Execution time Memory
826285 2023-08-15T12:18:15 Z 79brue Dancing Elephants (IOI11_elephants) C++17
50 / 100
 348 ms 4816 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int SZ_MIN = 300, SZ_MAX = 600;

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;
            }
        }

        if(sz < SZ_MAX) 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];
    }

    for(int i=0; i<k; i++){
        assert(groups[i]->sz);
        if(i+1<k) assert(groups[i]->arr[groups[i]->sz-1] <= groups[i+1]->arr[0]);
    }

    return c;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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

# Verdict Execution time Memory Grader output
1 Correct 0 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

# Verdict Execution time Memory Grader output
1 Correct 0 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 118 ms 3564 KB Output is correct
8 Correct 132 ms 3776 KB Output is correct
9 Correct 209 ms 2508 KB Output is correct
10 Correct 193 ms 4812 KB Output is correct
11 Correct 168 ms 4816 KB Output is correct
12 Correct 348 ms 3396 KB Output is correct
13 Correct 213 ms 4744 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 118 ms 3564 KB Output is correct
8 Correct 132 ms 3776 KB Output is correct
9 Correct 209 ms 2508 KB Output is correct
10 Correct 193 ms 4812 KB Output is correct
11 Correct 168 ms 4816 KB Output is correct
12 Correct 348 ms 3396 KB Output is correct
13 Correct 213 ms 4744 KB Output is correct
14 Incorrect 109 ms 3788 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 118 ms 3564 KB Output is correct
8 Correct 132 ms 3776 KB Output is correct
9 Correct 209 ms 2508 KB Output is correct
10 Correct 193 ms 4812 KB Output is correct
11 Correct 168 ms 4816 KB Output is correct
12 Correct 348 ms 3396 KB Output is correct
13 Correct 213 ms 4744 KB Output is correct
14 Incorrect 109 ms 3788 KB Output isn't correct
15 Halted 0 ms 0 KB -