Submission #638354

#	Time	Username	Problem	Language	Result	Execution time	Memory
638354		jiahng	The Potion of Great Power (CEOI20_potion)	C++14	0 / 100	518 ms	262144 KiB

potion

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int H[maxn], N, D;
unordered_set <int> st[maxn][2];
vpi updates[maxn];
void init(int N, int D, int H[]) {
    ::N = N; ::D = D;
    FOR(i,0,N-1) ::H[i] = H[i];
    FOR(i,0,N-1) updates[i].pb(pi(-1,-1));
}

void curseChanges(int U, int A[], int B[]) {
    FOR(i,0,U-1){
        if (updates[A[i]].back() != pi(-1,-1)) aFOR(j, st[updates[A[i]].back().f][updates[A[i]].back().s]) st[i][0].insert(j);
        if (updates[B[i]].back() != pi(-1,-1)) aFOR(j, st[updates[B[i]].back().f][updates[B[i]].back().s]) st[i][1].insert(j);

        if (st[i][0].find(B[i]) == st[i][0].end()) st[i][0].insert(B[i]);
        else st[i][0].erase(B[i]);

        if (st[i][1].find(A[i]) == st[i][1].end()) st[i][1].insert(A[i]);
        else st[i][1].erase(A[i]);

        updates[A[i]].pb(pi(i,0)); updates[B[i]].pb(pi(i,1));
    }


}

int question(int x, int y, int v) {
    pi xidx = *(--ubd(updates[x], pi(v, 2)));
    pi yidx = *(--ubd(updates[y], pi(v, 2)));

    set <int> xst, yst;
    if (xidx.f != -1) aFOR(i, st[xidx.f][xidx.s]) xst.insert(H[i]);
    if (yidx.f != -1) aFOR(i, st[yidx.f][yidx.s]) yst.insert(H[i]);

    int ans = INF;
    aFOR(i, xst){
        auto it = yst.lower_bound(i);
        if (it != yst.end()) ans = min(ans, *it - i);
        if (it != yst.begin()) ans = min(ans, abs(*(--it) - i));
    }
    //cout << "ASD" << ans << '\n';
    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