Submission #1218201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218201		__moin__	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	1016 ms	327680 KiB

potion

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

struct segtree_arr {
    int n;
    vector<int> vals;
    vector<int> left;
    vector<int> right;

    segtree_arr() {

    }

    segtree_arr(int N, int def) {
        n = N;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;
        vals.resize(2*n, -1);
        left.resize(2*n, -1);
        right.resize(2*n, -1);
        for (int i = 0; i < N; i++) {
            vals[n+i] = def;
        }
        for (int i = n-1; i >= 1; i--) {
            left[i] = 2*i;
            right[i] = 2*i+1;
        }
    }

    int add_node(int v, int l, int r) {
        vals.push_back(v);
        left.push_back(l);
        right.push_back(r);
        return vals.size()-1;
    }

    int set(int idx, int x, int l, int r, int i) {
        if (l + 1 == r) {
            return add_node(x, -1, -1);
        }
        int m = (l+r)/2;
        if (idx < m) {
            return add_node(-1, set(idx, x, l, m, left[i]), right[i]);
        } else {
            return add_node(-1, left[i], set(idx, x, m, r, right[i]));
        }
    }

    int get(int idx, int l, int r, int i) {
        if (l+1 == r) return vals[i];
        int m = (l+r)/2;
        if (idx < m) return get(idx, l, m, left[i]);
        else return get(idx, m, r, right[i]);
    }
};

vector<int> heights;

struct cmp {
    bool operator()(int x, int y) const {
        if (heights[x] == heights[y]) return x < y;
        return heights[x] < heights[y];
    }
};

vector<set<int,cmp>> adj_sets;
segtree_arr adj;

vector<int> v_roots;

void init(int N, int D, int H[]) {
    adj_sets.push_back({});
    adj = segtree_arr(N, 0);
    v_roots.push_back(1);
    heights.resize(N);
    for (int i = 0; i < N; i++) heights[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        int a = A[i], b = B[i];// a--; b--;
        set<int,cmp> sa = adj_sets[adj.get(a, 0, adj.n, v_roots.back())];
        set<int,cmp> sb = adj_sets[adj.get(b, 0, adj.n, v_roots.back())];
        if (sa.find(b) == sa.end()) {
            sa.insert(b);
            sb.insert(a);
        } else {
            sa.erase(b);
            sb.erase(a);
        }
        adj_sets.push_back(sa);
        adj_sets.push_back(sb);
        int tmp_root = adj.set(a, adj_sets.size()-2, 0, adj.n, v_roots.back());
        int new_root = adj.set(b, adj_sets.size()-1, 0, adj.n, tmp_root);
        v_roots.push_back(new_root);
    }
}

int question(int x, int y, int v) {
    // cerr << "X = " << x << ", Y = " << y << ", V = " << v << "\n";
    set<int,cmp> sx = adj_sets[adj.get(x, 0, adj.n, v_roots[v])];
    set<int,cmp> sy = adj_sets[adj.get(y, 0, adj.n, v_roots[v])];
    int min_diff = 1e9;
    for (int a : sx) {
        auto tmp = sy.lower_bound(a);
        if (tmp != sy.end()) min_diff = min(min_diff, abs(heights[a] - heights[*tmp]));
        if (tmp != sy.begin()) min_diff = min(min_diff, abs(heights[a] - heights[*(--tmp)]));
        // for (int b : sy) min_diff = min(min_diff, abs(heights[a] - heights[b]));
    }
    return min_diff;
}

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