oj.uz

Submission #939647

# Submission time Handle Problem Language Result Execution time Memory
939647 2024-03-06T16:00:12 Z haxorman Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 23396 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;
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 2 ms 12888 KB Output is correct
2 Correct 3 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 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 1958 ms 13752 KB Output is correct
8 Correct 2636 ms 14100 KB Output is correct
9 Correct 1352 ms 15768 KB Output is correct
10 Correct 682 ms 15956 KB Output is correct
11 Correct 517 ms 15704 KB Output is correct
12 Correct 2324 ms 15788 KB Output is correct
13 Correct 553 ms 15776 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 1958 ms 13752 KB Output is correct
8 Correct 2636 ms 14100 KB Output is correct
9 Correct 1352 ms 15768 KB Output is correct
10 Correct 682 ms 15956 KB Output is correct
11 Correct 517 ms 15704 KB Output is correct
12 Correct 2324 ms 15788 KB Output is correct
13 Correct 553 ms 15776 KB Output is correct
14 Correct 1681 ms 14160 KB Output is correct
15 Correct 2059 ms 14244 KB Output is correct
16 Correct 3713 ms 15768 KB Output is correct
17 Correct 3976 ms 16936 KB Output is correct
18 Correct 3717 ms 16948 KB Output is correct
19 Correct 4240 ms 16980 KB Output is correct
20 Correct 3907 ms 16948 KB Output is correct
21 Correct 3553 ms 16936 KB Output is correct
22 Correct 928 ms 17168 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 1958 ms 13752 KB Output is correct
8 Correct 2636 ms 14100 KB Output is correct
9 Correct 1352 ms 15768 KB Output is correct
10 Correct 682 ms 15956 KB Output is correct
11 Correct 517 ms 15704 KB Output is correct
12 Correct 2324 ms 15788 KB Output is correct
13 Correct 553 ms 15776 KB Output is correct
14 Correct 1681 ms 14160 KB Output is correct
15 Correct 2059 ms 14244 KB Output is correct
16 Correct 3713 ms 15768 KB Output is correct
17 Correct 3976 ms 16936 KB Output is correct
18 Correct 3717 ms 16948 KB Output is correct
19 Correct 4240 ms 16980 KB Output is correct
20 Correct 3907 ms 16948 KB Output is correct
21 Correct 3553 ms 16936 KB Output is correct
22 Correct 928 ms 17168 KB Output is correct
23 Execution timed out 9050 ms 23396 KB Time limit exceeded
24 Halted 0 ms 0 KB -