Submission #965491

#	Time	Username	Problem	Language	Result	Execution time	Memory
965491		Huseyn123	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	1922 ms	27144 KiB

potion

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int sz = 50;
vector<vector<int>> pre;
vector<int> e, vec, cnt;
int a[200001],b[200001];
vector<int> d[200001][2]; 

void init(int N, int D, int H[]) {
    pre.resize(N + 1);
    cnt.resize(N + 1, 0);
    for (int i = 0; i < N; i++) {
        vec.pb(H[i]);
    }
}

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        a[i] = A[i];
        b[i] = B[i];
    }
    for (int i = 0; i < U; i++) {
        pre[a[i]].pb(i);
        pre[b[i]].pb(i);
        if ((int)pre[a[i]].size() % sz == 0) {
            int h1 = pre[a[i]].size();
            int h = h1 - sz;
            e.clear();
            if (h != 0) {
                int h2 = 0;
                if (a[pre[a[i]][h - 1]] != a[i]) {
                    h2 = 1;
                }
                for (auto x : d[pre[a[i]][h - 1]][h2]) {
                    e.pb(x);
                    cnt[x]++;
                }
            }
            for (int j = h; j < h1; j++) {
                int h2 = a[pre[a[i]][j]];
                if (h2 == a[i]) {
                    h2 = b[pre[a[i]][j]];
                }
                cnt[h2]++;
                if (cnt[h2] == 1) {
                    e.pb(h2);
                }
            }
            for (auto x : e) {
                if (cnt[x] % 2) {
                    d[i][0].pb(x);
                }
                cnt[x] = 0;
            }
        }
        if ((int)pre[b[i]].size() % sz == 0) {
            int h1 = pre[b[i]].size();
            int h = h1 - sz;
            e.clear();
            if (h != 0) {
                int h2 = 0;
                if (a[pre[b[i]][h - 1]] != b[i]) {
                    h2 = 1;
                }
                for (auto x : d[pre[b[i]][h - 1]][h2]) {
                    e.pb(x);
                    cnt[x]++;
                }
            }
            for (int j = h; j < h1; j++) {
                int h2 = b[pre[b[i]][j]];
                if (h2 == b[i]) {
                    h2 = a[pre[b[i]][j]];
                }
                cnt[h2]++;
                if (cnt[h2] == 1) {
                    e.pb(h2);
                }
            }
            for (auto x : e) {
                if (cnt[x] % 2) {
                    d[i][1].pb(x);
                }
                cnt[x] = 0;
            }
        }
    }
}

int question(int x, int y, int v) {
    vector<int> d1, d2;
    if (v == 0) {
        return 1e9;
    }
    v--;
    auto it = upper_bound(pre[x].begin(), pre[x].end(), v);
    auto it1 = upper_bound(pre[y].begin(), pre[y].end(), v);
    if (it == pre[x].begin() || it1 == pre[y].begin()) {
        return 1e9;
    }
    int h = it - pre[x].begin();
    int h1 = it1 - pre[y].begin();
    int h2, h3;
    h2 = h - h % sz;
    h3 = h1 - h1 % sz;
    e.clear();
    if (h2 != 0) {
        int tp = 0;
        if (a[pre[x][h2 - 1]] != x) {
            tp = 1;
        }
        for (auto z : d[pre[x][h2 - 1]][tp]) {
            e.pb(z);
            cnt[z]++;
        }
    }
    for (int i = h2; i < h; i++) {
        int tp = a[pre[x][i]];
        if (tp == x) {
            tp = b[pre[x][i]];
        }
        cnt[tp]++;
        if (cnt[tp] == 1) {
            e.pb(tp);
        }
    }
    for (auto z : e) {
        if (cnt[z] % 2) {
            d1.pb(vec[z]);
        }
        cnt[z] = 0;
    }
    e.clear();
    if (h3 != 0) {
        int tp = 0;
        if (a[pre[y][h3 - 1]] != y) {
            tp = 1;
        }
        for (auto z : d[pre[y][h3 - 1]][tp]) {
            e.pb(z);
            cnt[z]++;
        }
    }
    for (int i = h3; i < h1; i++) {
        int tp = a[pre[y][i]];
        if (tp == y) {
            tp = b[pre[y][i]];
        }
        cnt[tp]++;
        if (cnt[tp] == 1) {
            e.pb(tp);
        }
    }
    for (auto z : e) {
        if (cnt[z] % 2) {
            d2.pb(vec[z]);
        }
        cnt[z] = 0;
    }
    if(d1.size()==0 || d2.size()==0){
    	return 1e9;
    }
    sort(d1.begin(),d1.end());
    sort(d2.begin(),d2.end());
    int res=1e9;
    int j=0;
    for(int i=0;i<(int)d1.size();i++){
    	while(j<(int)d2.size() && d1[i]>d2[j]){
    		j++;
    	}
    	if(j<(int)d2.size()){
    		res=min(res,d2[j]-d1[i]);
    	}
    }
    j=(int)d2.size()-1;
    for(int i=(int)d1.size()-1;i>=0;i--){
    	while(j>=0 && d1[i]<d2[j]){
    		j--;
    	}
    	if(j>=0){
    		res=min(res,d1[i]-d2[j]);
    	}
    }
    return res;
}

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