Submission #1159357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159357		aligay100infa	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	487 ms	327680 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 F first
#define S second

using namespace std;

typedef long long ll;

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

int sz = 0, root[N];

void upd(int pos, int val, int v, int &u, int tl = 1, int tr = n * d) {
	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;
}

void get(int l, int r, int v, int tl = 1, int tr = n * d) {
    if (!v || t[v].val == 0 || r < tl || tr < l) return;
    // cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << t[v].val << '\n';
    if (tl == tr) {
        mex.push_back(t[v].val);
        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++) {
        for (int j = 1; j <= d; j++) {
            s[i].insert({0, j});
        }
    }
    for (int i = 1; i <= n; i++) h[i] = H[i - 1];        
}

pair <bool, int> add(int a, int b) {
    auto it = s[a].lower_bound({b, 0});
    if (it == s[a].end() || (*it).F != b) {
        int id = (*s[a].begin()).S;
        s[a].erase(s[a].begin());
        s[a].insert({b, id});
        return {true, id};
    }
    int id = (*it).S;
    s[a].erase(it);
    s[a].insert({0, id});
    return {false, id};
}

void curseChanges(signed U, signed A[], signed B[]) {
    m = U;
    root[0] = ++sz;
    for (int i = 1; i <= m; i++) {
        ll a = A[i - 1] + 1, b = B[i - 1] + 1;
        pair <bool, int> cur = add(a, b);
        if (cur.F) upd((a - 1) * d + cur.S, b, root[i - 1], root[i]);
        else upd((a - 1) * d + cur.S, 0, root[i - 1], root[i]);
        // cout << "upd " << a << ' ' << b << ' ' << (a - 1) * d + cur.S << ' ' << (cur.F ? b : 0) << '\n';

        swap(a, b);
        cur = add(a, b);
        if (cur.F) upd((a - 1) * d + cur.S, b, root[i], root[i]);
        else upd((a - 1) * d + cur.S, 0, root[i], root[i]);
        // cout << "upd " << a << ' ' << b << ' ' << (a - 1) * d + cur.S << ' ' << (cur.F ? b : 0) << '\n';
    }
}

int question(signed x, signed y, signed v) {
    x++;
    y++;
    mex.clear();
    get((y - 1) * d + 1, y * d, root[v]);
    // cout << "sum v in time " << v << ' ' << t[root[v]].val << '\n';
    vector <int> act;
    for (int it: mex) {
        act.push_back(h[it]);
        // cout << y << ' ' << it << '\n';
    }
    sort(act.begin(), act.end());
    int ans = 1e9;
    if (!len(act)) return ans;
    mex.clear();
    get((x - 1) * d + 1, x * d, root[v]);
    for (int i: mex) {
        // 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: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30