Submission #900459

#	Time	Username	Problem	Language	Result	Execution time	Memory
900459		Dec0Dedd	The Potion of Great Power (CEOI20_potion)	C++14	0 / 100	3050 ms	12900 KiB

potion

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5+10;
const int INF = 1e9;

int n, d, h[N], a[N], b[N], c;

void init(int _n, int _d, int _h[]) {
    n=_n, d=_d;
    for (int i=0; i<n; ++i) h[i]=_h[i];
}

void curseChanges(int sz, int _a[], int _b[]) {
    c=sz;
    for (int i=1; i<=c; ++i) a[i]=_a[i-1], b[i]=_b[i-1];
}

int question(int x, int y, int v) {
    ++v;

    map<int, int> usx, usy;
    for (int i=1; i<=v; ++i) {
        if (a[i] == x) usx[b[i]]^=1;
        else if (b[i] == x) usx[a[i]]^=1;

        if (a[i] == y) usy[b[i]]^=1;
        else if (b[i] == y) usy[a[i]]^=1;
    } usx[x]=usy[y]=0;

    vector<int> hx, hy;
    for (int i=1; i<=v; ++i) {
        if (usx[a[i]]) hx.push_back(h[a[i]]);
        if (usx[b[i]]) hx.push_back(h[b[i]]);
        if (usy[a[i]]) hy.push_back(h[a[i]]);
        if (usy[b[i]]) hy.push_back(h[b[i]]);
    } sort(hx.begin(), hx.end()), sort(hy.begin(), hy.end());

    if (hx.empty() || hy.empty()) return INF;
    int ptr=0, ans=INF;

    for (auto u : hx) {
        while (ptr < (int)hy.size()) {
            if (hy[ptr] <= u) ++ptr;
            else break;
        }

        ans=min(ans, abs(u-hy[min((int)hy.size()-1, ptr)]));
        if (ptr > 0) ans=min(ans, abs(u-hy[ptr-1]));
    } return ans;
}

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