Submission #1113251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113251		Zero_OP	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	871 ms	35476 KiB

potion

#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);
}

bool duplicated(const vector<int>& A){
    for(int i = 0; i + 1 < (int)A.size(); ++i) if(A[i] == A[i + 1]) return true;
    return false;
}

bool intersect(const vector<int>& A, const vector<int>& B){
    //just for assertion
    for(auto x : A) if(binary_search(B.begin(), B.end(), x)) return true;
    return false;
}

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;
    }

    assert(!duplicated(old_candidates));
    assert(!duplicated(new_candidates));
    assert(!intersect(old_candidates, new_candidates));
    sort(new_candidates.begin(), new_candidates.end());

    blocks[u].emplace_back(old_candidates);
    merge_vector(blocks[u].back(), new_candidates);

//    cout << "addBlock " << u << '\n';
//    for(int i = sz - C; i < sz; ++i) cout << "(" << modification[u][i].first << ' ' << modification[u][i].second << ")\n";
//    for(int v : blocks[u].back()) cout << v << ' '; cout << '\n';
//    cout << '\n';
}

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);

//    cout << x << ' ' << y << '\n';
//    cout << "A : ";
//    for(auto it : A) cout << it << ' '; cout << '\n';
//
//    cout << "B : ";
//    for(auto it : B) cout << it << ' '; cout << '\n';

    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;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    int N, D, U, Q;
    cin >> N >> D >> U >> Q;

    int H[N];
    for(int i = 0; i < N; ++i) cin >> H[i];

    int A[U], B[U];
    for(int i = 0; i < U; ++i) cin >> A[i] >> B[i];

    init(N, D, H);
    curseChanges(U, A, B);

    for(int i = 0; i < Q; ++i){
        int x, y, v;
        cin >> x >> y >> v;
        cout << question(x, y, v) << '\n';
    }

    return 0;
}
#endif //LOCAL

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30