oj.uz

Submission #826007

# Submission time Handle Problem Language Result Execution time Memory
826007 2023-08-15T09:50:03 Z 79brue Dancing Elephants (IOI11_elephants) C++17
10 / 100
 0 ms 340 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, c = 1;
        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--;
            while(nxt[last] != last) last = nxt[last], c++;
            nxt[i] = last, cnt[i] = c;
        }
    }

    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(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

# Verdict Execution time Memory 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
0 / 16.0

# Verdict Execution time Memory 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 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory 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 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory 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 Incorrect 0 ms 340 KB Output isn't correct
5 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 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -