oj.uz

Submission #939670

# Submission time Handle Problem Language Result Execution time Memory
939670 2024-03-06T16:28:55 Z haxorman Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 23228 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][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;
    }
    
    vector<pair<int,int>> vec(n);
    for (int i = 0; i < n; ++i) {
        vec[i] = {pos[i], i};
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; ++i) {
        bkt[vec[i].second] = i/SZ;
        arr[i/SZ][sz[i/SZ]++] = vec[i];
    }

    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;
        }
    }
    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]);
            
            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 1 ms 10584 KB Output is correct
2 Correct 1 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 1 ms 10584 KB Output is correct
2 Correct 1 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 1 ms 10588 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 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 1 ms 10588 KB Output is correct
7 Correct 2175 ms 13584 KB Output is correct
8 Correct 2946 ms 14092 KB Output is correct
9 Correct 1399 ms 15600 KB Output is correct
10 Correct 849 ms 15592 KB Output is correct
11 Correct 706 ms 15592 KB Output is correct
12 Correct 2799 ms 15596 KB Output is correct
13 Correct 791 ms 15600 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 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 1 ms 10588 KB Output is correct
7 Correct 2175 ms 13584 KB Output is correct
8 Correct 2946 ms 14092 KB Output is correct
9 Correct 1399 ms 15600 KB Output is correct
10 Correct 849 ms 15592 KB Output is correct
11 Correct 706 ms 15592 KB Output is correct
12 Correct 2799 ms 15596 KB Output is correct
13 Correct 791 ms 15600 KB Output is correct
14 Correct 1926 ms 13816 KB Output is correct
15 Correct 2201 ms 14132 KB Output is correct
16 Correct 4169 ms 15596 KB Output is correct
17 Correct 4494 ms 16688 KB Output is correct
18 Correct 4361 ms 16688 KB Output is correct
19 Correct 5040 ms 16728 KB Output is correct
20 Correct 4435 ms 16684 KB Output is correct
21 Correct 4224 ms 16696 KB Output is correct
22 Correct 1246 ms 16688 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 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 1 ms 10588 KB Output is correct
7 Correct 2175 ms 13584 KB Output is correct
8 Correct 2946 ms 14092 KB Output is correct
9 Correct 1399 ms 15600 KB Output is correct
10 Correct 849 ms 15592 KB Output is correct
11 Correct 706 ms 15592 KB Output is correct
12 Correct 2799 ms 15596 KB Output is correct
13 Correct 791 ms 15600 KB Output is correct
14 Correct 1926 ms 13816 KB Output is correct
15 Correct 2201 ms 14132 KB Output is correct
16 Correct 4169 ms 15596 KB Output is correct
17 Correct 4494 ms 16688 KB Output is correct
18 Correct 4361 ms 16688 KB Output is correct
19 Correct 5040 ms 16728 KB Output is correct
20 Correct 4435 ms 16684 KB Output is correct
21 Correct 4224 ms 16696 KB Output is correct
22 Correct 1246 ms 16688 KB Output is correct
23 Execution timed out 9016 ms 23228 KB Time limit exceeded
24 Halted 0 ms 0 KB -