Submission #1214778

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

potion

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

struct node {
    short val = 0;
    //int nextl = -1;
    int nextr = -1;
    int l = -1, r = -1;
};

struct st {
    vector<node> v;
    int as;
};

st build (int n) {
    int as = 1 << (__lg(n) + 1);
    vector<node> v (as*2);
    for (int i = as-1; i > 0; i--) {
        v[i].l = i*2;
        v[i].r = i*2 + 1;
    }
    return {v, as};
}

pair<int, int> update (st &seg, int id, int d, int i, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    int nid = seg.v.size();
    seg.v.push_back(seg.v[i]);
    if (lo == hi-1) {
        seg.v[nid].val += d;
        return {nid, nid};
    }
    int mid = (lo + hi) / 2;
    int qa, qb;
    if (id < mid) {
        tie(qa, qb) = update(seg, id, d, seg.v[nid].l, lo, mid);
        seg.v[nid].l = qa;
    } else {
        tie(qa, qb) = update(seg, id, d, seg.v[nid].r, mid, hi);
        seg.v[nid].r = qa;
    }
    seg.v[nid].val = seg.v[seg.v[nid].l].val + seg.v[seg.v[nid].r].val;
    return {nid, qb};
}

int query (st &seg, int id, int i, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (lo == hi-1) return i;
    int mid = (lo + hi) / 2;
    if (id < mid) {
        return query(seg, id, seg.v[i].l, lo, mid);
    } else {
        return query(seg, id, seg.v[i].r, mid, hi);
    }
}

int searchl (st &seg, int id, int i, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (lo >= id) return -1;
    if (lo == hi-1) {
        if (seg.v[i].val > 0) return lo;
        else return -1;
    }
    int mid = (lo + hi) / 2;
    int lid = seg.v[i].l;
    int rid = seg.v[i].r;
    int sol = -1;
    if (seg.v[rid].val > 0) {
        sol = searchl(seg, id, rid, mid, hi);
    }
    if (sol == -1 && seg.v[lid].val > 0) {
        sol = searchl(seg, id, lid, lo, mid);
    }
    return sol;
}

int searchr (st &seg, int id, int i, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (hi <= id+1) return -1;
    if (lo == hi-1) {
        if (seg.v[i].val > 0) return lo;
        else return -1;
    }
    int mid = (lo + hi) / 2;
    int lid = seg.v[i].l;
    int rid = seg.v[i].r;
    int sol = -1;
    if (seg.v[lid].val > 0) {
        sol = searchr(seg, id, lid, lo, mid);
    }
    if (sol == -1 && seg.v[rid].val > 0) {
        sol = searchr(seg, id, rid, mid, hi);
    }
    
    return sol;
}

int n, d;
//vector<int> vh;
vector<int> vhs;
vector<int> vid;

st seg;
vector<vector<pair<int, int>>> vroot; // day - root

int add_friend (int a, int b) {
    int root = vroot[a].back().second;
    int l = searchl(seg, b+1, root);
    int r = searchr(seg, b+1, root);
    int nl, nr, ni;
    tie(root, nl) = update(seg, l, 0, root);
    tie(root, nr) = update(seg, r, 0, root);
    tie(root, ni) = update(seg, b+1, 1, root);
    seg.v[nl].nextr = b+1;
    /*seg.v[nr].nextl = b+1;
    seg.v[ni].nextl = l;*/
    seg.v[ni].nextr = r;
    return root;
}

int rem_friend (int a, int b) {
    int root = vroot[a].back().second;
    int l = searchl(seg, b+1, root);
    int r = searchr(seg, b+1, root);
    int nl, nr, ni;
    tie(root, nl) = update(seg, l, 0, root);
    tie(root, nr) = update(seg, r, 0, root);
    tie(root, ni) = update(seg, b+1, -1, root);
    seg.v[nl].nextr = r;
    //seg.v[nr].nextl = l;
    return root;
}

void init(int N, int D, int H[]) {
    n = N;
    d = D;
    vhs = vector<int> (N);
    vector<pair<int, int>> vq;
    for (int i = 0; i < N; i++) {
        vhs[i] = H[i];
        vq.push_back({vhs[i], i});
    }
    sort(vhs.begin(), vhs.end());
    sort(vq.begin(), vq.end());
    vid = vector<int> (n);
    for (int i = 0; i < N; i++) {
        vid[vq[i].second] = i;
    }

    seg = build(n+2);
    int root = 1;
    int l, r;
    tie(root, l) = update(seg, 0, 1, 1);
    tie(root, r) = update(seg, n+1, 1, root);
    seg.v[l].nextr = n+1;
    //seg.v[r].nextl = 0;
    vroot = vector<vector<pair<int, int>>> (n, vector<pair<int, int>> {{-1, root}});
}

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        int a = vid[A[i]];
        int b = vid[B[i]];
        if (seg.v[query(seg, b+1, vroot[a].back().second)].val == 1) {
            vroot[a].push_back({i, rem_friend(a, b)});
            vroot[b].push_back({i, rem_friend(b, a)});
        } else {
            vroot[a].push_back({i, add_friend(a, b)});
            vroot[b].push_back({i, add_friend(b, a)});
        }
    }
}

int question(int x, int y, int v) {
    int x1 = vid[x];
    int y1 = vid[y];
    int rootx = (--upper_bound(vroot[x1].begin(), vroot[x1].end(), make_pair(v, 0)))->second;
    int rooty = (--upper_bound(vroot[y1].begin(), vroot[y1].end(), make_pair(v, 0)))->second;
    int l = query(seg, 0, rootx);
    int r = query(seg, 0, rooty);
    int sol = 1e9;
    int curl = 0;
    int curr = 0;
    while (seg.v[l].nextr != -1) {
        curl = seg.v[l].nextr;
        l = query(seg, seg.v[l].nextr, rootx);
        if (seg.v[l].nextr == -1) continue;
        while (seg.v[r].nextr != -1 && seg.v[r].nextr <= curl) {
            curr = seg.v[r].nextr;
            r = query(seg, seg.v[r].nextr, rooty);
        }
        if (curr != 0 && curr != n+1) {
            int nsol = vhs[curl-1] - vhs[curr - 1];
            sol = min(sol, nsol);
        }
        if (seg.v[r].nextr != -1 && seg.v[r].nextr != 0 && seg.v[r].nextr != n+1) {
            int nsol = abs(vhs[curl-1] - vhs[seg.v[r].nextr - 1]);
            sol = min(sol, nsol);
        }
    }
    return sol;
}

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