oj.uz

Submission #939653

# Submission time Handle Problem Language Result Execution time Memory
939653 2024-03-06T16:06:40 Z haxorman Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 24132 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[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();
        arr[i].reserve(2*SZ);
    }
    
    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:61: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]
   61 |     for (int j = 0; j < arr[bkt[i]].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 3 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14488 KB Output is correct
6 Correct 3 ms 14440 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 3 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14488 KB Output is correct
6 Correct 3 ms 14440 KB Output is correct
7 Correct 1968 ms 15112 KB Output is correct
8 Correct 2640 ms 15376 KB Output is correct
9 Correct 1369 ms 17072 KB Output is correct
10 Correct 678 ms 17104 KB Output is correct
11 Correct 503 ms 17068 KB Output is correct
12 Correct 2297 ms 17240 KB Output is correct
13 Correct 561 ms 17240 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 3 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14488 KB Output is correct
6 Correct 3 ms 14440 KB Output is correct
7 Correct 1968 ms 15112 KB Output is correct
8 Correct 2640 ms 15376 KB Output is correct
9 Correct 1369 ms 17072 KB Output is correct
10 Correct 678 ms 17104 KB Output is correct
11 Correct 503 ms 17068 KB Output is correct
12 Correct 2297 ms 17240 KB Output is correct
13 Correct 561 ms 17240 KB Output is correct
14 Correct 1678 ms 15372 KB Output is correct
15 Correct 2033 ms 15676 KB Output is correct
16 Correct 3887 ms 17172 KB Output is correct
17 Correct 3959 ms 18032 KB Output is correct
18 Correct 3840 ms 18120 KB Output is correct
19 Correct 4546 ms 18112 KB Output is correct
20 Correct 4065 ms 18112 KB Output is correct
21 Correct 3723 ms 18120 KB Output is correct
22 Correct 936 ms 18120 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 3 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14488 KB Output is correct
6 Correct 3 ms 14440 KB Output is correct
7 Correct 1968 ms 15112 KB Output is correct
8 Correct 2640 ms 15376 KB Output is correct
9 Correct 1369 ms 17072 KB Output is correct
10 Correct 678 ms 17104 KB Output is correct
11 Correct 503 ms 17068 KB Output is correct
12 Correct 2297 ms 17240 KB Output is correct
13 Correct 561 ms 17240 KB Output is correct
14 Correct 1678 ms 15372 KB Output is correct
15 Correct 2033 ms 15676 KB Output is correct
16 Correct 3887 ms 17172 KB Output is correct
17 Correct 3959 ms 18032 KB Output is correct
18 Correct 3840 ms 18120 KB Output is correct
19 Correct 4546 ms 18112 KB Output is correct
20 Correct 4065 ms 18112 KB Output is correct
21 Correct 3723 ms 18120 KB Output is correct
22 Correct 936 ms 18120 KB Output is correct
23 Execution timed out 9063 ms 24132 KB Time limit exceeded
24 Halted 0 ms 0 KB -