제출 #349062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349062		dolphingarlic	The Potion of Great Power (CEOI20_potion)	C++14	56 / 100	1698 ms	262148 KiB

potion

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

const int INF = 1e9;

struct Node {
    int mn, mx, cnt;
    Node *l, *r;

    Node(int val, int c): mn(val), mx(val), cnt(c), l(nullptr), r(nullptr) {}
    Node(Node *ll, Node *rr) {
        l = ll, r = rr;
        mn = INF, mx = -INF;
        if (l && l->cnt) mn = min(mn, l->mn), mx = max(mx, l->mx), cnt = 1;
        if (r && r->cnt) mn = min(mn, r->mn), mx = max(mx, r->mx), cnt = 1;
    }
};

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->cnt + 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->cnt) return {-INF, INF};
    if (pos < node->mn) return {-INF, node->mn};
    if (pos >= node->mx) return {node->mx, 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