Submission #349057

#	Time	Username	Problem	Language	Result	Execution time	Memory
349057		dolphingarlic	The Potion of Great Power (CEOI20_potion)	C++14	56 / 100	1691 ms	262148 KiB

potion

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

const int INF = 1e9;

struct Node {
    pair<int, int> mn, mx;
    Node *l, *r;

    Node(pair<int, int> val): mn(val), mx(val), l(nullptr), r(nullptr) {}
    Node(Node *ll, Node *rr) {
        l = ll, r = rr;
        mn = {INF, 0}, mx = {-INF, 0};
        if (l && l->mn.second) mn = min(mn, l->mn), mx = max(mx, l->mx);
        if (r && r->mn.second) mn = min(mn, r->mn), mx = max(mx, r->mx);
    }
};

vector<int> comp;
int idx[100000];
map<int, Node*> persist_roots[100000];

Node* build(int l = 1, int r = comp.size()) {
    if (l == r) return new Node({l, 0});
    int mid = (l + r) / 2;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node* update(Node *node, int pos, int val, int l = 1, int r = comp.size()) {
    if (l == r) return new Node({l, node->mn.second + val});
    int mid = (l + r) / 2;
    if (pos > mid) return new Node(node->l, update(node->r, pos, val, mid + 1, r));
    return new Node(update(node->l, pos, val, l, mid), node->r);
}

pair<int, int> query(Node *node, int pos, int l = 1, int r = comp.size()) {
    if (!node->mn.second) return {-INF, INF};
    if (pos < node->mn.first) return {-INF, node->mn.first};
    if (pos >= node->mx.first) return {node->mx.first, INF};
    int mid = (l + r) / 2;
    pair<int, int> l_ans = query(node->l, pos, l, mid);
    pair<int, int> r_ans = query(node->r, pos, mid + 1, r);
    return {max(l_ans.first, r_ans.first), min(l_ans.second, r_ans.second)};
}

void init(int N, int D, int H[]) {
    for (int i = 0; i < N; i++) comp.push_back(H[i]);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    Node *root = build();
    for (int i = 0; i < N; i++) {
        idx[i] = lower_bound(comp.begin(), comp.end(), H[i]) - comp.begin() + 1;
        persist_roots[i][0] = root;
    }
}

set<int> trust[100000];

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        if (trust[A[i]].find(B[i]) == trust[A[i]].end()) {
            trust[A[i]].insert(B[i]);
            trust[B[i]].insert(A[i]);
            persist_roots[A[i]][i + 1] = update(persist_roots[A[i]].rbegin()->second, idx[B[i]], 1);
            persist_roots[B[i]][i + 1] = update(persist_roots[B[i]].rbegin()->second, idx[A[i]], 1);
        } else {
            trust[A[i]].erase(B[i]);
            trust[B[i]].erase(A[i]);
            persist_roots[A[i]][i + 1] = update(persist_roots[A[i]].rbegin()->second, idx[B[i]], -1);
            persist_roots[B[i]][i + 1] = update(persist_roots[B[i]].rbegin()->second, idx[A[i]], -1);
        }
    }
}

int question(int x, int y, int v) {
    Node *x_root = prev(persist_roots[x].upper_bound(v))->second;
    Node *y_root = prev(persist_roots[y].upper_bound(v))->second;
    
    int ans = INF;
    for (int i = query(x_root, -1).second; i != INF; i = query(x_root, i).second) {
        pair<int, int> y_closest = query(y_root, i);
        if (y_closest.first != -INF)
            ans = min(ans, comp[i - 1] - comp[y_closest.first - 1]);
        if (y_closest.second != INF)
            ans = min(ans, comp[y_closest.second - 1] - comp[i - 1]);
    }
    return ans;
}

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