Submission #417928

#	Time	Username	Problem	Language	Result	Execution time	Memory
417928		ACmachine	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	863 ms	262148 KiB

potion

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FOR(i, n, 0, 1)
#define pb push_back
#define ff first
#define ss second
const int INF = (int)2e9 + 15;
struct segtree{
    vector<vector<int>> tree;
    vector<int> lch, rch;
    int n;
    int create_new(){
        tree.pb(vector<int>());
        lch.pb(-1); rch.pb(-1);
        return (int)tree.size() - 1;
    }
    segtree(){}
    segtree(int sz){
        n = 1;
        while(n < sz) n *= 2;
        create_new();
    }
    void upd(int l, int r, int val){upd0(l, r, 0, n, 0, val);}
    void upd0(int l, int r, int beg, int end, int v, int val){
        if(beg >= l && end <= r){
            tree[v].pb(val);
            return;
        }
        if(beg >= r || end <= l) 
            return;
        int mid = (beg + end) >> 1;
        if(lch[v] == -1 && !(beg >= r || mid <= l)){
            int id = create_new();
            lch[v] = id;
            upd0(l, r, beg, mid, lch[v], val);
        }
        else if(!(beg >= r || mid <= l)){
            upd0(l, r, beg, mid, lch[v], val);
        }
        if(rch[v] == -1 && !(mid >= r || end <= l)){
            int id = create_new();
            rch[v] = id;
            upd0(l, r, mid, end, rch[v], val);
        }
        else if(!(mid >= r || end <= l)){
            upd0(l, r, mid, end, rch[v], val);
        }
    }
    void query0(int pos, int beg, int end, int v, vector<int> &res){
        if(beg > pos || end <= pos)
            return;
        for(int x : tree[v]) 
            res.pb(x);
        if(beg == pos && end == pos + 1) 
            return;
        int mid = (beg + end) >> 1;
        if(lch[v] != -1)
            query0(pos, beg, mid, lch[v], res);
        if(rch[v] != -1)
            query0(pos, mid, end, rch[v], res);
    }
};
vector<segtree> segtrees;
int n;
vector<int> h;
void init(int N, int d, int H[]) {
    n = N;
    REP(i, N) 
        h.pb(H[i]);
}

void curseChanges(int U, int A[], int B[]) {
    segtrees.resize(n, segtree(U + 5));
    map<array<int, 2>, int> edges;
    FOR(i, 1, U + 1, 1){
        array<int, 2> tm = {A[i - 1], B[i - 1]};
        if(tm[0] > tm[1]) swap(tm[0], tm[1]);
        if(edges.find(tm) != edges.end()){
            segtrees[tm[0]].upd(edges[tm], i, h[tm[1]]);
            segtrees[tm[1]].upd(edges[tm], i, h[tm[0]]);
            edges.erase(tm);
        }
        else{
            edges[tm] = i;
        }
    }
    for(auto x : edges){
        auto tm = x.ff;
        segtrees[tm[0]].upd(x.ss, U + 1, h[tm[1]]);
        segtrees[tm[1]].upd(x.ss, U + 1, h[tm[0]]);
    }
}

int question(int x, int y, int v) {
    vector<int> f;
    vector<int> s;
    segtrees[x].query0(v, 0, segtrees[x].n, 0, f);
    segtrees[y].query0(v, 0, segtrees[y].n, 0, s);
    if(f.empty() || s.empty()){
        return (int)1e9;
    } 
    sort(f.begin(), f.end());
    sort(s.begin(), s.end());
    int ans = (int)1e9 + 5;
    for(int x : f){
        int id = lower_bound(s.begin(), s.end(), x) - s.begin();
        if(id > 0){
            ans = min(ans, abs(x - s[id - 1]));
        }
        if(id < (int)s.size()){
            ans = min(ans, abs(x - s[id]));
        }
    }
    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