oj.uz

Submission #826281

# Submission time Handle Problem Language Result Execution time Memory
826281 2023-08-15T12:15:16 Z 79brue Dancing Elephants (IOI11_elephants) C++17
50 / 100
 309 ms 4824 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];
    }

    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 119 ms 3512 KB Output is correct
8 Correct 155 ms 3768 KB Output is correct
9 Correct 205 ms 2472 KB Output is correct
10 Correct 184 ms 4804 KB Output is correct
11 Correct 155 ms 4824 KB Output is correct
12 Correct 309 ms 3308 KB Output is correct
13 Correct 196 ms 4760 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 119 ms 3512 KB Output is correct
8 Correct 155 ms 3768 KB Output is correct
9 Correct 205 ms 2472 KB Output is correct
10 Correct 184 ms 4804 KB Output is correct
11 Correct 155 ms 4824 KB Output is correct
12 Correct 309 ms 3308 KB Output is correct
13 Correct 196 ms 4760 KB Output is correct
14 Incorrect 106 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 119 ms 3512 KB Output is correct
8 Correct 155 ms 3768 KB Output is correct
9 Correct 205 ms 2472 KB Output is correct
10 Correct 184 ms 4804 KB Output is correct
11 Correct 155 ms 4824 KB Output is correct
12 Correct 309 ms 3308 KB Output is correct
13 Correct 196 ms 4760 KB Output is correct
14 Incorrect 106 ms 3788 KB Output isn't correct
15 Halted 0 ms 0 KB -