oj.uz

Submission #559643

# Submission time Handle Problem Language Result Execution time Memory
559643 2022-05-10T10:57:00 Z ngpin04 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 2599 ms 14556 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
const int Nmax = 15e4 + 5;
const int Q = 400;
const int K = 1100;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

#include "elephants.h"
//#include "grader.cpp"

int ptr[Nmax / K][2 * K + 5];
int dp[Nmax / K][2 * K + 5];
int b[Nmax / K][2 * K + 5];
int v[Nmax / K][2 * K + 5];

pair <int, int> pos[Nmax];

int sz[Nmax];
int x[Nmax];
int n,l,cnt,cntb;

void build(int p, int b[], int ptr[], int dp[], int v[]) {
    dp[sz[p]] = 0;
    for (int i = sz[p] - 1, j = sz[p]; i >= 0; i--) {
        while (v[j - 1] - v[i] > l)
            j--;
        if (j == sz[p]) {
            dp[i] = 0;
            ptr[i] = i;
        } else {
            ptr[i] = ptr[j];
            dp[i] = dp[j] + 1;
        }
    }
}

void del(int i) {
    int p = pos[i].fi;
    int ind = pos[i].se;
    for (int j = ind; j + 1 < sz[p]; j++)
        b[p][j] = b[p][j + 1];
    sz[p]--;

    for (int j = 0; j < sz[p]; j++) {
        pos[b[p][j]] = mp(p, j);
        v[p][j] = x[b[p][j]];
    }

    build(p, b[p], ptr[p], dp[p], v[p]);
}

int getmax(int p) {
    return v[p][sz[p] - 1];
}

void add(int i) {
    int p = 0;
    while (p < cntb && (sz[p] > 0 && getmax(p) < x[i]))
        p++;

    int ind = -1;
    while (ind + 1 < sz[p] && v[p][ind + 1] < x[i])
        ind++;

    for (int j = sz[p]; j - 1 > ind; j--)
        b[p][j] = b[p][j - 1];

    b[p][ind + 1] = i;
    sz[p]++;
    for (int j = 0; j < sz[p]; j++) {
        pos[b[p][j]] = mp(p, j);
        v[p][j] = x[b[p][j]];
    }

    build(p, b[p], ptr[p], dp[p], v[p]);
}

void rebuild() {
    vector <int> ind;

    for (int i = 0; i <= cntb; i++) {
        for (int j = 0; j < sz[i]; j++)
            ind.push_back(b[i][j]);
        sz[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int p = i / K;
        int it = ind[i];
        pos[it] = mp(p, sz[p]);
        b[p][sz[p]++] = it;
    }

    for (int i = 0; i <= cntb; i++) {
        for (int j = 0; j < sz[i]; j++) 
            v[i][j] = x[b[i][j]];

        build(i, b[i], ptr[i], dp[i], v[i]);
    }
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    for (int i = 0; i < n; i++)
        x[i] = X[i];

    cntb = (n - 1) / K;

    vector <int> ind(n, 0);
    iota(ALL(ind), 0);
    sort(ALL(ind), [](int i, int j) {
        return x[i] < x[j];
    });

    for (int i = 0; i < n; i++) {
        int p = i / K;
        int it = ind[i];
        pos[it] = mp(p, sz[p]);
        b[p][sz[p]++] = it;
    }

    for (int i = 0; i <= cntb; i++) {
        for (int j = 0; j < sz[i]; j++) 
            v[i][j] = x[b[i][j]];

        build(i, b[i], ptr[i], dp[i], v[i]);
    }
}

int update(int i, int y) {
    cnt++;
    del(i);
    x[i] = y;
    add(i);

    int res = 0;
    int p = 0;
    int cur = 0;

    while (true) {
        res += dp[p][cur];
        cur = ptr[p][cur];
        int nxt = p + 1;
        while (nxt <= cntb && 
        (sz[nxt] == 0 || getmax(nxt) - v[p][cur] <= l)) 
            nxt++;

        res++;
        if (nxt > cntb) 
            break;
        
        int lo = -1;
        int hi = sz[nxt] - 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (v[nxt][mid] - v[p][cur] <= l)
                lo = mid;
            else
                hi = mid;
        }

        cur = hi;
        p = nxt;
    }

    if (cnt == Q) {
        cnt = 0;
        rebuild();
    }
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 746 ms 1836 KB Output is correct
8 Correct 765 ms 3024 KB Output is correct
9 Correct 880 ms 5248 KB Output is correct
10 Correct 754 ms 5028 KB Output is correct
11 Correct 691 ms 5048 KB Output is correct
12 Correct 1390 ms 5160 KB Output is correct
13 Correct 698 ms 4836 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 746 ms 1836 KB Output is correct
8 Correct 765 ms 3024 KB Output is correct
9 Correct 880 ms 5248 KB Output is correct
10 Correct 754 ms 5028 KB Output is correct
11 Correct 691 ms 5048 KB Output is correct
12 Correct 1390 ms 5160 KB Output is correct
13 Correct 698 ms 4836 KB Output is correct
14 Correct 1042 ms 3804 KB Output is correct
15 Correct 1213 ms 3876 KB Output is correct
16 Correct 2527 ms 5828 KB Output is correct
17 Correct 2507 ms 7304 KB Output is correct
18 Correct 2599 ms 7308 KB Output is correct
19 Correct 1286 ms 7496 KB Output is correct
20 Correct 2506 ms 7308 KB Output is correct
21 Correct 2298 ms 7264 KB Output is correct
22 Correct 1313 ms 7036 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 746 ms 1836 KB Output is correct
8 Correct 765 ms 3024 KB Output is correct
9 Correct 880 ms 5248 KB Output is correct
10 Correct 754 ms 5028 KB Output is correct
11 Correct 691 ms 5048 KB Output is correct
12 Correct 1390 ms 5160 KB Output is correct
13 Correct 698 ms 4836 KB Output is correct
14 Correct 1042 ms 3804 KB Output is correct
15 Correct 1213 ms 3876 KB Output is correct
16 Correct 2527 ms 5828 KB Output is correct
17 Correct 2507 ms 7304 KB Output is correct
18 Correct 2599 ms 7308 KB Output is correct
19 Correct 1286 ms 7496 KB Output is correct
20 Correct 2506 ms 7308 KB Output is correct
21 Correct 2298 ms 7264 KB Output is correct
22 Correct 1313 ms 7036 KB Output is correct
23 Incorrect 105 ms 14556 KB Output isn't correct
24 Halted 0 ms 0 KB -