oj.uz

Submission #939648

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

const int mxN = 150007;
const int SZ = 500;

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

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

        if (val >= arr[b].back().first) {
            to[arr[b][i].second] = val;
            cnt[arr[b][i].second] = 1;
        }
        else {
            auto it = upper_bound(arr[b].begin(), arr[b].end(),
                                                  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) {
        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:60: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]
   60 |     for (int j = 0; j < arr[bkt[i]].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12696 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4088 ms 14124 KB Output is correct
8 Correct 4154 ms 14020 KB Output is correct
9 Correct 1704 ms 15652 KB Output is correct
10 Correct 832 ms 15448 KB Output is correct
11 Correct 587 ms 15904 KB Output is correct
12 Correct 3164 ms 15944 KB Output is correct
13 Correct 682 ms 15656 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12696 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4088 ms 14124 KB Output is correct
8 Correct 4154 ms 14020 KB Output is correct
9 Correct 1704 ms 15652 KB Output is correct
10 Correct 832 ms 15448 KB Output is correct
11 Correct 587 ms 15904 KB Output is correct
12 Correct 3164 ms 15944 KB Output is correct
13 Correct 682 ms 15656 KB Output is correct
14 Correct 2557 ms 13904 KB Output is correct
15 Correct 2801 ms 14544 KB Output is correct
16 Correct 4690 ms 15644 KB Output is correct
17 Correct 5138 ms 17004 KB Output is correct
18 Correct 5014 ms 16888 KB Output is correct
19 Correct 6286 ms 16756 KB Output is correct
20 Correct 5000 ms 17068 KB Output is correct
21 Correct 4677 ms 17144 KB Output is correct
22 Correct 1090 ms 16752 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12696 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4088 ms 14124 KB Output is correct
8 Correct 4154 ms 14020 KB Output is correct
9 Correct 1704 ms 15652 KB Output is correct
10 Correct 832 ms 15448 KB Output is correct
11 Correct 587 ms 15904 KB Output is correct
12 Correct 3164 ms 15944 KB Output is correct
13 Correct 682 ms 15656 KB Output is correct
14 Correct 2557 ms 13904 KB Output is correct
15 Correct 2801 ms 14544 KB Output is correct
16 Correct 4690 ms 15644 KB Output is correct
17 Correct 5138 ms 17004 KB Output is correct
18 Correct 5014 ms 16888 KB Output is correct
19 Correct 6286 ms 16756 KB Output is correct
20 Correct 5000 ms 17068 KB Output is correct
21 Correct 4677 ms 17144 KB Output is correct
22 Correct 1090 ms 16752 KB Output is correct
23 Execution timed out 9021 ms 23088 KB Time limit exceeded
24 Halted 0 ms 0 KB -