제출 #674464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674464		cheeheng	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	7477 ms	14968 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

//typedef pair<int, int> ii;

int n;
int l;
int X1[150005];
int X2[150005];

// m groups of elephants, m is about sqrt(max_n)
// Y[i] represents positions of elephants
// Y[i] sorted in increasing order and last element of Y[i] is at most Y[i+1][0].
int Y[505][1005];
int nextY[505][1005];
int distY[505][1005];
int lastY[505][1005];
int lenY[505];
int m = 2;
int resetCnt;

int opCnt = 0;

int sortedX[150005];

void findNext(int i) {
    int ptr = 0;
    int len = lenY[i];
    for (int j = 0; j < len; j++) {
        while (ptr < len && Y[i][ptr] <= Y[i][j]+l) {
            ptr++;
        }
        nextY[i][j] = ptr;
    }
    for (int j = len-1; j >= 0; j--) {
        int nextPos = nextY[i][j];
        if (nextPos == len) {
            distY[i][j] = 0;
            lastY[i][j] = j;
        } else {
            distY[i][j] = distY[i][nextPos]+1;
            lastY[i][j] = lastY[i][nextPos];
        }
    }
}

void reset() {
    for (int i = 0; i < m; i++) {
        lenY[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int indx = (long long)i*m/n;
        Y[indx][lenY[indx]++] = sortedX[i];
        //printf("reset: Y[%d][%d]=%d\n", indx, lenY[indx]-1, sortedX[i]);
    }

    for (int i = 0; i < m; i++) {
        findNext(i);
    }
}

void printY() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < lenY[i]; j++) {
            printf("Y[%d][%d]=%d\n", i, j, Y[i][j]);
        }
    }
}

// smallest (indx1, indx2) such that Y[indx1][indx2] >= val
void find1(int val, int &indx1, int &indx2) {
    // find largest x such that Y[x][0] < val
    // Y[x][0] < val and Y[x+1][0] >= val
    int lo = 0;
    int hi = m-1;
    while (lo < hi) {
        int mid = (lo+hi+1)>>1;
        if (Y[mid][0] >= val) {
            hi = mid-1;
        } else {
            lo = mid;
        }
    }

    indx1 = lo;
    if (indx1 == m) {
        indx2 = 0;
        return;
    } else {
        indx2 = lower_bound(Y[indx1], Y[indx1]+lenY[indx1], val) - Y[indx1];
        if (indx2 == lenY[indx1]) {
            indx1++;
            indx2 = 0;
        }
        return;
    }
}

void insert1(int val) {
    int indx1, indx2;
    find1(val, indx1, indx2);

    if (indx1 == m) {
        indx1 = m-1;
        indx2 = lenY[indx1];
    }

    for (int j = lenY[indx1]-1; j >= indx2; j--) {
        Y[indx1][j+1] = Y[indx1][j];
    }
    Y[indx1][indx2] = val;
    lenY[indx1]++;

    findNext(indx1);
}

void remove1(int val) {
    int indx1, indx2;
    find1(val, indx1, indx2);

    //printf("remove1: (val, indx1, indx2) = (%d, %d, %d)\n", val, indx1, indx2);

    for (int j = indx2; j < lenY[indx1]; j++) {
        Y[indx1][j] = Y[indx1][j+1];
    }
    lenY[indx1]--;

    findNext(indx1);
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    m = min(max(sqrt(n), 1.0), n/2.0);
    //m = 1;
    resetCnt = n/m-1;
    for (int i = 0; i < n; i++) {
        X1[i] = X[i];
        sortedX[i] = X[i];
    }
    opCnt = 0;
    reset();
}

int update(int i, int y) {
    opCnt++;

    // update Y list
    remove1(X1[i]);

    //printf("op %d\n", opCnt);
    //printY();
    insert1(y);
    //printY();

    X1[i] = y;

    // find answer
    int curI = 0;
    int curJ = 0;
    int ans = 1;
    while (curI < m) {
        ans += distY[curI][curJ];
        curJ = lastY[curI][curJ];
        int target = Y[curI][curJ]+l+1;
        find1(target, curI, curJ);
        //printf("next: (%d, %d)\n", curI, curJ);
        if (curI < m) {
            ans += 1;
        }
    }

    if (opCnt%resetCnt == 0) {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < lenY[i]; j++) {
                sortedX[cnt++] = Y[i][j];
                if (cnt >= 2) {
                    assert(sortedX[cnt-1] >= sortedX[cnt-2]);
                }
            }
        }
        reset();
    }
    return ans;
}

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