oj.uz

Submission #674464

# Submission time Handle Problem Language Result Execution time Memory
674464 2022-12-24T10:35:40 Z cheeheng Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7477 ms 14968 KB 
#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.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
16.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 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 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 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 424 ms 2824 KB Output is correct
8 Correct 512 ms 3212 KB Output is correct
9 Correct 792 ms 6472 KB Output is correct
10 Correct 766 ms 6436 KB Output is correct
11 Correct 606 ms 6304 KB Output is correct
12 Correct 1014 ms 6476 KB Output is correct
13 Correct 1161 ms 6156 KB Output is correct

Subtask #4
47.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 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 424 ms 2824 KB Output is correct
8 Correct 512 ms 3212 KB Output is correct
9 Correct 792 ms 6472 KB Output is correct
10 Correct 766 ms 6436 KB Output is correct
11 Correct 606 ms 6304 KB Output is correct
12 Correct 1014 ms 6476 KB Output is correct
13 Correct 1161 ms 6156 KB Output is correct
14 Correct 415 ms 4984 KB Output is correct
15 Correct 861 ms 5312 KB Output is correct
16 Correct 1469 ms 7116 KB Output is correct
17 Correct 1707 ms 8288 KB Output is correct
18 Correct 1779 ms 8100 KB Output is correct
19 Correct 1418 ms 8396 KB Output is correct
20 Correct 1684 ms 8168 KB Output is correct
21 Correct 1694 ms 8188 KB Output is correct
22 Correct 1988 ms 7732 KB Output is correct

Subtask #5
3.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 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 424 ms 2824 KB Output is correct
8 Correct 512 ms 3212 KB Output is correct
9 Correct 792 ms 6472 KB Output is correct
10 Correct 766 ms 6436 KB Output is correct
11 Correct 606 ms 6304 KB Output is correct
12 Correct 1014 ms 6476 KB Output is correct
13 Correct 1161 ms 6156 KB Output is correct
14 Correct 415 ms 4984 KB Output is correct
15 Correct 861 ms 5312 KB Output is correct
16 Correct 1469 ms 7116 KB Output is correct
17 Correct 1707 ms 8288 KB Output is correct
18 Correct 1779 ms 8100 KB Output is correct
19 Correct 1418 ms 8396 KB Output is correct
20 Correct 1684 ms 8168 KB Output is correct
21 Correct 1694 ms 8188 KB Output is correct
22 Correct 1988 ms 7732 KB Output is correct
23 Correct 4927 ms 14968 KB Output is correct
24 Correct 5273 ms 14964 KB Output is correct
25 Correct 4658 ms 14968 KB Output is correct
26 Correct 5250 ms 14964 KB Output is correct
27 Correct 5229 ms 14880 KB Output is correct
28 Correct 690 ms 6112 KB Output is correct
29 Correct 630 ms 6096 KB Output is correct
30 Correct 704 ms 6100 KB Output is correct
31 Correct 640 ms 6096 KB Output is correct
32 Correct 4072 ms 14412 KB Output is correct
33 Correct 2571 ms 13728 KB Output is correct
34 Correct 4601 ms 14608 KB Output is correct
35 Correct 2478 ms 14904 KB Output is correct
36 Correct 865 ms 14384 KB Output is correct
37 Correct 4840 ms 14792 KB Output is correct
38 Correct 6823 ms 13612 KB Output is correct
39 Correct 5164 ms 14640 KB Output is correct
40 Correct 7477 ms 13636 KB Output is correct
41 Correct 5563 ms 14360 KB Output is correct
42 Correct 5766 ms 14620 KB Output is correct