제출 #115764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
115764		songc	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	26 / 100	19 ms	1784 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, K, Sq, M, Q;
int A[150505];
int T[150505];

struct Eleph{
    int x, s, p;
    bool operator<(const Eleph &r)const{
        return x < r.x;
    }
};
Eleph B[400][400];
int sz[400];

void calc(int t){
    int k=sz[t]-1;
    for (int j=k; j>=0; j--){
        while (B[t][j].x + K < B[t][k].x) k--;
        if (k == sz[t]-1) B[t][j].s = 1, B[t][j].p = B[t][j].x + K;
        else B[t][j].s = B[t][k+1].s + 1, B[t][j].p = B[t][k+1].p;
    }
}

void init(int n, int l, int X[]){
    N=n, K=l;
    Sq = sqrt(N);
    M = (N+Sq-1)/Sq;
    for (int i=0; i<N; i++) {
        B[i/Sq][sz[i/Sq]++].x = X[i];
        if (!Q) A[i] = X[i];
    }
    for (int i=0; i<M; i++) calc(i);
}

void del(int x){
    int k;
    for (k=0; k<M; k++) {
        if (sz[k] == 0) continue;
        if (lower_bound(B[k], B[k]+sz[k], (Eleph){x, 0, 0})->x == x) break;
    }
    sz[k]--;
    for (int i=lower_bound(B[k], B[k]+sz[k], (Eleph){x, 0, 0}) - B[k]; i<sz[k]; i++){
        B[k][i] = B[k][i+1];
    }
    calc(k);
}

void add(int x){
    int k;
    for (k=0; k<M-1; k++){
        if (sz[k] == 0) continue;
        if (lower_bound(B[k], B[k]+sz[k], (Eleph){x, 0, 0}) != B[k]+sz[k]) break;
    }
    B[k][sz[k]++] = (Eleph){x, 0, 0};
    for (int i=sz[k]-1; i>0; i--){
        if (B[k][i-1].x > B[k][i].x) swap(B[k][i], B[k][i-1]);
    }
    calc(k);
}

int update(int i, int y){
    del(A[i]);
    A[i] = y;
    add(y);
    Q++;

    if (Q % 400 == 0){
        int t=0;
        for (int i=0; i<M; i++) {
            for (Eleph it : B[i]) T[t++] = it.x;
            sz[i] = 0;
        }
        init(N, K, T);
    }

    int p=-1, ans=0;
    for (int i=0; i<M; i++){
        if (sz[i] == 0) continue;
        int k = upper_bound(B[i], B[i]+sz[i], (Eleph){p, 0, 0}) - B[i];
        if (k == sz[i]) continue;
        ans += B[i][k].s;
        p = B[i][k].p;
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3