oj.uz

Submission #939641

# Submission time Handle Problem Language Result Execution time Memory
939641 2024-03-06T15:53:26 Z haxorman Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 30548 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];
set<pair<int,int>> st;
vector<pair<int,int>> arr[SZ];

void fix(int b) {
    for (int i = arr[b].size()-1; i >= 0; --i) {
        int val = arr[b][i].first + l;
        auto it = upper_bound(arr[b].begin(), arr[b].end(), make_pair(val,INT_MAX));

        if (it == arr[b].end()) {
            to[arr[b][i].second] = val;
            cnt[arr[b][i].second] = 1;
        }
        else {
            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) {
        arr[i].clear();
    }
    
    auto it = st.begin();
    for (int i = 0; i < n; ++i) {
        bkt[(*it).second] = i/SZ;
        arr[i/SZ].push_back(*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 < arr[bkt[i]].size(); ++j) {
        if (arr[bkt[i]][j].second == i) {
            arr[bkt[i]].erase(arr[bkt[i]].begin() + j);
            break;
        }
    }
    st.erase({pos[i], i});
    fix(bkt[i]);
    
    for (int b = 0; b < SZ; ++b) {
        if (b == SZ-1 || (arr[b].size() && arr[b].back().first > y)) {
            bkt[i] = b;
            arr[b].push_back({pos[i] = y, i});
            sort(arr[b].begin(), arr[b].end());
            
            st.insert({pos[i], i});
            fix(b);
            break;
        }
    }
    
    int ans = 0, cur = -1;
    for (int b = 0; b < SZ; ++b) {
        if (arr[b].size() && arr[b].back().first > cur) {
            auto it = upper_bound(arr[b].begin(), arr[b].end(),
                                                  make_pair(cur,INT_MAX));

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

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

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int j = 0; j < arr[bkt[i]].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 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 2 ms 10584 KB Output is correct
2 Correct 4 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 2 ms 10584 KB Output is correct
2 Correct 4 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 1946 ms 13640 KB Output is correct
8 Correct 2654 ms 15184 KB Output is correct
9 Correct 1350 ms 17324 KB Output is correct
10 Correct 726 ms 16980 KB Output is correct
11 Correct 647 ms 17048 KB Output is correct
12 Correct 2275 ms 17212 KB Output is correct
13 Correct 660 ms 16728 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 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 1946 ms 13640 KB Output is correct
8 Correct 2654 ms 15184 KB Output is correct
9 Correct 1350 ms 17324 KB Output is correct
10 Correct 726 ms 16980 KB Output is correct
11 Correct 647 ms 17048 KB Output is correct
12 Correct 2275 ms 17212 KB Output is correct
13 Correct 660 ms 16728 KB Output is correct
14 Correct 1803 ms 17632 KB Output is correct
15 Correct 2021 ms 17640 KB Output is correct
16 Correct 3672 ms 19628 KB Output is correct
17 Correct 3884 ms 21504 KB Output is correct
18 Correct 3786 ms 20952 KB Output is correct
19 Correct 4259 ms 21140 KB Output is correct
20 Correct 3815 ms 21028 KB Output is correct
21 Correct 3509 ms 20988 KB Output is correct
22 Correct 1064 ms 20568 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 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 1946 ms 13640 KB Output is correct
8 Correct 2654 ms 15184 KB Output is correct
9 Correct 1350 ms 17324 KB Output is correct
10 Correct 726 ms 16980 KB Output is correct
11 Correct 647 ms 17048 KB Output is correct
12 Correct 2275 ms 17212 KB Output is correct
13 Correct 660 ms 16728 KB Output is correct
14 Correct 1803 ms 17632 KB Output is correct
15 Correct 2021 ms 17640 KB Output is correct
16 Correct 3672 ms 19628 KB Output is correct
17 Correct 3884 ms 21504 KB Output is correct
18 Correct 3786 ms 20952 KB Output is correct
19 Correct 4259 ms 21140 KB Output is correct
20 Correct 3815 ms 21028 KB Output is correct
21 Correct 3509 ms 20988 KB Output is correct
22 Correct 1064 ms 20568 KB Output is correct
23 Execution timed out 9031 ms 30548 KB Time limit exceeded
24 Halted 0 ms 0 KB -