제출 #1159297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159297		aligay100infa	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	2139 ms	249660 KiB

potion

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls tl, tm
#define rs tm + 1, tr
#define ll long long
#define int long long

using namespace std;

namespace {
    const int N = 2e5 + 3;
    int n, d, m, h[N], cnt[N];
    set <int> s[N];
    vector <ll> mex;
    struct node{
        bool val;
        int l, r;
        node () : val(0), l(0), r(0) {}
    } t[N * 50];
}

int sz = 0, root[N];

void upd(int pos, bool val, int v, int &u, ll tl = 1, ll tr = 1ll * n * n) {
	u = ++sz;
	if (tl == tr) {
		t[u].val = val;
		return;
	}
	if (pos <= tm) {
		t[u].r = t[v].r;
		upd(pos, val, t[v].l, t[u].l, ls);
	} else {
		t[u].l = t[v].l;
		upd(pos, val, t[v].r, t[u].r, rs);
	}
	int lv = t[u].l, rv = t[u].r;
	t[u].val = t[lv].val | t[rv].val;
}

bool fnd(int pos, int v, ll tl = 1, ll tr = 1ll * n * n) {
    if (!v || !t[v].val) return false;
    if (tl == tr) return t[v].val;
    if (pos <= tm) return fnd(pos, t[v].l, ls);
    else return fnd(pos, t[v].r, rs);
}

void get(ll l, ll r, int v, ll tl = 1, ll tr = 1ll * n * n) {
    if (!v || !t[v].val || r < tl || tr < l) return;
    if (tl == tr) {
        mex.push_back(tl);
        return;
    }
    get(l, r, t[v].l, ls);
    get(l, r, t[v].r, rs);
}

void init(signed N, signed D, signed H[]) {
    n = N;
    d = D;
    for (int i = 1; i <= n; i++) {
        h[i] = H[i - 1];
    }
}

void curseChanges(signed U, signed A[], signed B[]) {
    m = U;
    root[0] = ++sz;
    for (int i = 1; i <= m; i++) {
        int a = A[i - 1] + 1, b = B[i - 1] + 1;
        int rot = root[i - 1];
        if (!fnd((a - 1) * n + b, root[i - 1])) {
            upd((a - 1) * n + b, 1, root[i - 1], root[i]);
            rot = root[i];
        } else {
            upd((a - 1) * n + b, 0, root[i - 1], root[i]);
            rot = root[i];
        }
        swap(a, b);
        if (!fnd((a - 1) * n + b, root[i - 1])) {
            upd((a - 1) * n + b, 1, rot, root[i]);
        } else {
            upd((a - 1) * n + b, 0, rot, root[i]);
        }
    }
}

int question(signed x, signed y, signed v) {
    x++;
    y++;
    mex.clear();
    get(1ll * (y - 1) * n + 1, y * n, root[v]);
    vector <int> act;
    for (ll it: mex) {
        act.push_back(h[it - (y - 1) * n]);
        // cout << y << ' ' << it - (y - 1) * n << '\n';
    }
    sort(act.begin(), act.end());
    int ans = 1e9;
    if (!len(act)) return ans;
    mex.clear();
    get(1ll * (x - 1) * n + 1, x * n, root[v]);
    for (ll it: mex) {
        ll i = it - (x - 1) * n;
        // cout << x << ' ' << i << '\n';
        int l = 0, r = len(act) - 1;
        while (l + 1 < r) {
            int md = l + r >> 1;
            if (h[i] <= act[md]) r = md;
            else l = md;
        }
        ans = min({ans, abs(h[i] - act[l]), abs(h[i] - act[r])});
    }

    return ans;
}

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