oj.uz

Submission #939649

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

const int mxN = 150007;
const int SZ = 300;

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 3 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 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 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 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 1650 ms 13828 KB Output is correct
8 Correct 2053 ms 14160 KB Output is correct
9 Correct 1107 ms 16148 KB Output is correct
10 Correct 609 ms 15920 KB Output is correct
11 Correct 469 ms 15920 KB Output is correct
12 Correct 2225 ms 15696 KB Output is correct
13 Correct 500 ms 15924 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 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 1650 ms 13828 KB Output is correct
8 Correct 2053 ms 14160 KB Output is correct
9 Correct 1107 ms 16148 KB Output is correct
10 Correct 609 ms 15920 KB Output is correct
11 Correct 469 ms 15920 KB Output is correct
12 Correct 2225 ms 15696 KB Output is correct
13 Correct 500 ms 15924 KB Output is correct
14 Correct 1205 ms 14080 KB Output is correct
15 Correct 1651 ms 14304 KB Output is correct
16 Correct 3086 ms 15924 KB Output is correct
17 Correct 3362 ms 17140 KB Output is correct
18 Correct 3235 ms 17152 KB Output is correct
19 Correct 3194 ms 17136 KB Output is correct
20 Correct 3323 ms 17136 KB Output is correct
21 Correct 2975 ms 17132 KB Output is correct
22 Correct 831 ms 17232 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 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 1650 ms 13828 KB Output is correct
8 Correct 2053 ms 14160 KB Output is correct
9 Correct 1107 ms 16148 KB Output is correct
10 Correct 609 ms 15920 KB Output is correct
11 Correct 469 ms 15920 KB Output is correct
12 Correct 2225 ms 15696 KB Output is correct
13 Correct 500 ms 15924 KB Output is correct
14 Correct 1205 ms 14080 KB Output is correct
15 Correct 1651 ms 14304 KB Output is correct
16 Correct 3086 ms 15924 KB Output is correct
17 Correct 3362 ms 17140 KB Output is correct
18 Correct 3235 ms 17152 KB Output is correct
19 Correct 3194 ms 17136 KB Output is correct
20 Correct 3323 ms 17136 KB Output is correct
21 Correct 2975 ms 17132 KB Output is correct
22 Correct 831 ms 17232 KB Output is correct
23 Incorrect 77 ms 23888 KB Output isn't correct
24 Halted 0 ms 0 KB -