oj.uz

Submission #1113252

# Submission time Handle Problem Language Result Execution time Memory
1113252 2024-11-16T08:51:14 Z Zero_OP The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 867 ms 35136 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
const int MAXQ = 2e5 + 5;
const int C = 50;

int N, D, H[MAXN], pos[MAXN];
vector<int> modified_time[MAXN];
vector<pair<int, int>> modification[MAXN];
vector<vector<int>> blocks[MAXN];

void init(int _N, int _D, int _H[]){
    N = _N;
    D = _D;
    copy(_H, _H + N, H);

    vector<pair<int, int>> v;
    for(int i = 0; i < N; ++i){
        v.emplace_back(H[i], i);
    }

    sort(v.begin(), v.end());
    sort(H, H + N);
    for(int i = 0; i < N; ++i){
        pos[v[i].second] = i;
    }
}

bool on[MAXN], used[MAXN];

void merge_vector(vector<int>& A, const vector<int>& B){
    vector<int> result;
    int i = 0, j = 0;
    while(i < (int)A.size() || j < (int)B.size()){
        if(i == (int)A.size()) result.emplace_back(B[j++]);
        else if(j == (int)B.size()) result.emplace_back(A[i++]);
        else if(A[i] < B[j]) result.emplace_back(A[i++]);
        else result.emplace_back(B[j++]);
    }
    swap(result, A);
}

void addBlock(int u){
    for(int v : blocks[u].back()) on[v] = 1, used[v] = true;
    int sz = (int)modification[u].size();
    vector<int> cur;
    for(int i = sz - C; i < sz; ++i){
        assert(i >= 0);
        int type, v;
        tie(type, v) = modification[u][i];

        if(!used[v]) used[v] = true, cur.push_back(v);

        if(type == -1) on[v] = false;
        if(type == +1) on[v] = true;
    }

    vector<int> old_candidates, new_candidates;
    for(int v : blocks[u].back()) {
        if(on[v]) old_candidates.emplace_back(v);
        on[v] = used[v] = false;
    }
    for(int v : cur) {
        if(on[v]) new_candidates.emplace_back(v);
        on[v] = used[v] = false;
    }

    sort(new_candidates.begin(), new_candidates.end());
    blocks[u].emplace_back(old_candidates);
    merge_vector(blocks[u].back(), new_candidates);
}

void curseChanges(int U, int A[], int B[]){
    for(int i = 0; i < N; ++i){
        modified_time[i].emplace_back(0);
        blocks[i].emplace_back();
    }

    set<pair<int, int>> pairs;

    for(int i = 0; i < U; ++i){
        int u = A[i], v = B[i];
        u = pos[u]; v = pos[v];
        modified_time[u].emplace_back(i + 1);
        modified_time[v].emplace_back(i + 1);

        if(u > v) swap(u, v);
        if(pairs.count({u, v})){
            modification[u].emplace_back(-1, v);
            modification[v].emplace_back(-1, u);
            pairs.erase({u, v});
        } else{
            modification[u].emplace_back(+1, v);
            modification[v].emplace_back(+1, u);
            pairs.insert({u, v});
        }

        if((int)modification[u].size() % C == 0) addBlock(u);
        if((int)modification[v].size() % C == 0) addBlock(v);
    }
}

vector<int> A, B;

void replay(vector<int>& result, int u, int n_version){
    if(modification[u].empty()) return;
    int B = (n_version) / C;
    int mod = (n_version) % C;

    for(int v : blocks[u][B]){
        on[v] = true;
        used[v] = true;
    }

    vector<int> cur;

    for(int t = 0; t < mod; ++t){
        int i = B * C + t;

        int type, v;
        tie(type, v) = modification[u][i];

        if(!used[v]){
            cur.emplace_back(v);
            used[v] = true;
        }

        if(type == -1) on[v] = false;
        if(type == +1) on[v] = true;
    }

    vector<int> old_candidates, new_candidates;
    for(int v : blocks[u][B]){
        if(on[v]) old_candidates.push_back(v);
        on[v] = used[v] = false;
    }

    for(int v : cur){
        if(on[v]) new_candidates.push_back(v);
        on[v] = used[v] = false;
    }

    sort(new_candidates.begin(), new_candidates.end());
    result = old_candidates;
    merge_vector(result, new_candidates);
}

int question(int x, int y, int v){
    x = pos[x]; y = pos[y];
    int p = upper_bound(modified_time[x].begin(), modified_time[x].end(), v) - modified_time[x].begin() - 1;
    int q = upper_bound(modified_time[y].begin(), modified_time[y].end(), v) - modified_time[y].begin() - 1;
    assert(p >= 0 && q >= 0);
    vector<int>().swap(A);
    vector<int>().swap(B);

    replay(A, x, p);
    replay(B, y, q);
  
    if(A.empty() && B.empty()) return (int)1e9;

    int ans = (int)1e9;
    int ptr = 0;
    for(int i = 0; i < (int)A.size(); ++i){
        while(ptr < (int)B.size() && B[ptr] < A[i]) ++ptr;
        if(ptr < (int)B.size()) ans = min(ans, abs(H[A[i]] - H[B[ptr]]));
        if(ptr - 1 >= 0) ans = min(ans, abs(H[A[i]] - H[B[ptr - 1]]));
    }

    return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7504 KB Output is correct
2 Correct 7 ms 7504 KB Output is correct
3 Correct 8 ms 7504 KB Output is correct
4 Correct 40 ms 15080 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 35100 KB Output is correct
2 Correct 406 ms 34884 KB Output is correct
3 Correct 210 ms 22448 KB Output is correct
4 Correct 511 ms 26044 KB Output is correct
5 Correct 369 ms 27016 KB Output is correct
6 Correct 813 ms 32952 KB Output is correct
7 Correct 485 ms 27312 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 35024 KB Output is correct
2 Correct 678 ms 30640 KB Output is correct
3 Correct 550 ms 29728 KB Output is correct
4 Correct 755 ms 32800 KB Output is correct
5 Correct 405 ms 35136 KB Output is correct
6 Correct 787 ms 33000 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9216 KB Output is correct
2 Correct 91 ms 8704 KB Output is correct
3 Correct 131 ms 8528 KB Output is correct
4 Correct 270 ms 8960 KB Output is correct
5 Correct 274 ms 9464 KB Output is correct
6 Correct 105 ms 8528 KB Output is correct
7 Correct 253 ms 8740 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 8 ms 7504 KB Output is correct
3 Correct 7 ms 7504 KB Output is correct
4 Correct 8 ms 7504 KB Output is correct
5 Correct 40 ms 15080 KB Output is correct
6 Correct 433 ms 35100 KB Output is correct
7 Correct 406 ms 34884 KB Output is correct
8 Correct 210 ms 22448 KB Output is correct
9 Correct 511 ms 26044 KB Output is correct
10 Correct 369 ms 27016 KB Output is correct
11 Correct 813 ms 32952 KB Output is correct
12 Correct 485 ms 27312 KB Output is correct
13 Correct 349 ms 35024 KB Output is correct
14 Correct 678 ms 30640 KB Output is correct
15 Correct 550 ms 29728 KB Output is correct
16 Correct 755 ms 32800 KB Output is correct
17 Correct 405 ms 35136 KB Output is correct
18 Correct 787 ms 33000 KB Output is correct
19 Correct 61 ms 9216 KB Output is correct
20 Correct 91 ms 8704 KB Output is correct
21 Correct 131 ms 8528 KB Output is correct
22 Correct 270 ms 8960 KB Output is correct
23 Correct 274 ms 9464 KB Output is correct
24 Correct 105 ms 8528 KB Output is correct
25 Correct 253 ms 8740 KB Output is correct
26 Correct 425 ms 26424 KB Output is correct
27 Correct 693 ms 29652 KB Output is correct
28 Correct 713 ms 34792 KB Output is correct
29 Correct 521 ms 26184 KB Output is correct
30 Correct 867 ms 33040 KB Output is correct
31 Correct 727 ms 30732 KB Output is correct
32 Correct 830 ms 33004 KB Output is correct