oj.uz

Submission #939666

# Submission time Handle Problem Language Result Execution time Memory
939666 2024-03-06T16:19:57 Z haxorman Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 28104 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 150007;
const int SZ = 388;

int n, l, step, pos[mxN], bkt[mxN], to[mxN], cnt[mxN], sz[mxN];
set<pair<int,int>> st;
pair<int,int> arr[SZ][3*SZ];

void fix(int b) {
    for (int i = sz[b]-1; i >= 0; --i) {
        int val = arr[b][i].first + l;

        if (val >= arr[b][sz[b]-1].first) {
            to[arr[b][i].second] = val;
            cnt[arr[b][i].second] = 1;
        }
        else {
            auto it = upper_bound(arr[b],arr[b]+sz[b],make_pair(val,INT_MAX));

            to[arr[b][i].second] = to[(*it).second];
            cnt[arr[b][i].second] = cnt[(*it).second] + 1;
        }
    }
}

void construct() {
    for (int i = 0; i < SZ; ++i) {
        sz[i] = 0;
    }
    
    auto it = st.begin();
    for (int i = 0; i < n; ++i) {
        bkt[(*it).second] = i/SZ;
        arr[i/SZ][sz[i/SZ]++] = *it;
        
        advance(it, 1);
    }

    for (int b = 0; b < SZ; ++b) {
        fix(b);
    }
}

void init(int N, int L, int X[]) {
    n = N, l = L;
    
    for (int i = 0; i < n; ++i) {
        pos[i] = X[i];
        st.insert({pos[i], i});
    }

    construct();
}

int update(int i, int y) {
    for (int j = 0; j < sz[bkt[i]]; ++j) {
        if (arr[bkt[i]][j].second == i) {
            arr[bkt[i]][j] = {INT_MAX,INT_MAX};
            sort(arr[bkt[i]], arr[bkt[i]]+sz[bkt[i]]);
            sz[bkt[i]]--;
            break;
        }
    }
    st.erase({pos[i], i});
    fix(bkt[i]);
    
    for (int b = 0; b < SZ; ++b) {
        if (b == SZ-1 || (sz[b] && arr[b][sz[b]-1].first > y)) {
            bkt[i] = b;
            arr[b][sz[b]++] = {pos[i] = y, i};
            sort(arr[b], arr[b]+sz[b]);
            
            st.insert({pos[i], i});
            fix(b);
            break;
        }
    }
    
    int ans = 0, cur = -1;
    for (int b = 0; b < SZ; ++b) {
        if (sz[b] && arr[b][sz[b]-1].first > cur) {
            auto it = upper_bound(arr[b],arr[b]+sz[b],make_pair(cur,INT_MAX));

            ans += cnt[(*it).second];
            cur = to[(*it).second];
        }
    }

    step++;
    if (step == SZ) {
        construct();
        step = 0;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12812 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12812 KB Output is correct
7 Correct 2193 ms 17832 KB Output is correct
8 Correct 2970 ms 17824 KB Output is correct
9 Correct 1398 ms 19312 KB Output is correct
10 Correct 678 ms 19316 KB Output is correct
11 Correct 515 ms 19312 KB Output is correct
12 Correct 2498 ms 19312 KB Output is correct
13 Correct 558 ms 19312 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12812 KB Output is correct
7 Correct 2193 ms 17832 KB Output is correct
8 Correct 2970 ms 17824 KB Output is correct
9 Correct 1398 ms 19312 KB Output is correct
10 Correct 678 ms 19316 KB Output is correct
11 Correct 515 ms 19312 KB Output is correct
12 Correct 2498 ms 19312 KB Output is correct
13 Correct 558 ms 19312 KB Output is correct
14 Correct 1803 ms 20100 KB Output is correct
15 Correct 2192 ms 20308 KB Output is correct
16 Correct 3859 ms 21448 KB Output is correct
17 Correct 4170 ms 22304 KB Output is correct
18 Correct 3895 ms 22296 KB Output is correct
19 Correct 4875 ms 22300 KB Output is correct
20 Correct 4073 ms 22308 KB Output is correct
21 Correct 3831 ms 22304 KB Output is correct
22 Correct 897 ms 22096 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12812 KB Output is correct
7 Correct 2193 ms 17832 KB Output is correct
8 Correct 2970 ms 17824 KB Output is correct
9 Correct 1398 ms 19312 KB Output is correct
10 Correct 678 ms 19316 KB Output is correct
11 Correct 515 ms 19312 KB Output is correct
12 Correct 2498 ms 19312 KB Output is correct
13 Correct 558 ms 19312 KB Output is correct
14 Correct 1803 ms 20100 KB Output is correct
15 Correct 2192 ms 20308 KB Output is correct
16 Correct 3859 ms 21448 KB Output is correct
17 Correct 4170 ms 22304 KB Output is correct
18 Correct 3895 ms 22296 KB Output is correct
19 Correct 4875 ms 22300 KB Output is correct
20 Correct 4073 ms 22308 KB Output is correct
21 Correct 3831 ms 22304 KB Output is correct
22 Correct 897 ms 22096 KB Output is correct
23 Execution timed out 9053 ms 28104 KB Time limit exceeded
24 Halted 0 ms 0 KB -