oj.uz

Submission #939702

# Submission time Handle Problem Language Result Execution time Memory
939702 2024-03-06T16:44:11 Z haxorman Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7047 ms 24820 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[SZ];
set<pair<int,int>> st;
pair<int,int> arr[SZ][2*SZ+7];

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

        while (ind && val < arr[b][ind-1].first) {
            --ind;
        }

        if (val >= arr[b][sz[b]-1].first) {
            to[arr[b][i].second] = val;
            cnt[arr[b][i].second] = 1;
        }
        else {
            to[arr[b][i].second] = to[arr[b][ind].second];
            cnt[arr[b][i].second] = cnt[arr[b][ind].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;
        
        it++;
    }

    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 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 940 ms 13484 KB Output is correct
8 Correct 1220 ms 13908 KB Output is correct
9 Correct 771 ms 18328 KB Output is correct
10 Correct 353 ms 18324 KB Output is correct
11 Correct 351 ms 18004 KB Output is correct
12 Correct 1047 ms 18328 KB Output is correct
13 Correct 359 ms 18208 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 940 ms 13484 KB Output is correct
8 Correct 1220 ms 13908 KB Output is correct
9 Correct 771 ms 18328 KB Output is correct
10 Correct 353 ms 18324 KB Output is correct
11 Correct 351 ms 18004 KB Output is correct
12 Correct 1047 ms 18328 KB Output is correct
13 Correct 359 ms 18208 KB Output is correct
14 Correct 1018 ms 14744 KB Output is correct
15 Correct 1030 ms 15012 KB Output is correct
16 Correct 1924 ms 18580 KB Output is correct
17 Correct 1998 ms 19512 KB Output is correct
18 Correct 1896 ms 19516 KB Output is correct
19 Correct 2214 ms 19512 KB Output is correct
20 Correct 1804 ms 19516 KB Output is correct
21 Correct 1831 ms 19524 KB Output is correct
22 Correct 683 ms 19260 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 940 ms 13484 KB Output is correct
8 Correct 1220 ms 13908 KB Output is correct
9 Correct 771 ms 18328 KB Output is correct
10 Correct 353 ms 18324 KB Output is correct
11 Correct 351 ms 18004 KB Output is correct
12 Correct 1047 ms 18328 KB Output is correct
13 Correct 359 ms 18208 KB Output is correct
14 Correct 1018 ms 14744 KB Output is correct
15 Correct 1030 ms 15012 KB Output is correct
16 Correct 1924 ms 18580 KB Output is correct
17 Correct 1998 ms 19512 KB Output is correct
18 Correct 1896 ms 19516 KB Output is correct
19 Correct 2214 ms 19512 KB Output is correct
20 Correct 1804 ms 19516 KB Output is correct
21 Correct 1831 ms 19524 KB Output is correct
22 Correct 683 ms 19260 KB Output is correct
23 Correct 4172 ms 24820 KB Output is correct
24 Correct 5149 ms 24816 KB Output is correct
25 Correct 3677 ms 24812 KB Output is correct
26 Correct 2705 ms 24812 KB Output is correct
27 Correct 7047 ms 24812 KB Output is correct
28 Correct 2916 ms 12724 KB Output is correct
29 Correct 2971 ms 12728 KB Output is correct
30 Correct 3043 ms 12728 KB Output is correct
31 Correct 3144 ms 12728 KB Output is correct
32 Correct 2192 ms 24560 KB Output is correct
33 Correct 1890 ms 24048 KB Output is correct
34 Correct 2292 ms 24552 KB Output is correct
35 Correct 1892 ms 24812 KB Output is correct
36 Correct 2292 ms 24556 KB Output is correct
37 Correct 6042 ms 24560 KB Output is correct
38 Correct 2302 ms 24108 KB Output is correct
39 Correct 5659 ms 24408 KB Output is correct
40 Correct 2357 ms 24040 KB Output is correct
41 Correct 6053 ms 24556 KB Output is correct
42 Correct 6004 ms 24560 KB Output is correct