Submission #294245

#	Time	Username	Problem	Language	Result	Execution time	Memory
294245		TheEpicCowOfLife	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	1756 ms	82076 KiB

potion

#include <cstdio>
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int n,u,q;
int h[100005]; //.H
typedef pair<int,int> pii;

int ol[2][100005]; // output lists for iteration.

/*
DUDE THIS IS SO COOL I'M LITERALLY INVENTING AN ENTIRELY NEW DATA STRUCTURE:
I AM AN ACTUAL GENIUS.
Description: A persistent singly linked list
Operations: 
Find root at time T, O(logmax(T)) I guess.
Advance iterator forward. O(1)
Insert a node between two existing nodes at time T O(1) amortised
remove a node. O(1) amortised.

O(n) memory.
*/


// height,id
/*
Pseudocode:
Function:
Generate a link from x to y:
if x is saturated, gen new node for x, link to y, run recursively on x's newest par.

Analysis: Nodes will go from unsaturated -> saturated -> new node.
Each call will only saturate one additional node.
Boom O(1).

Add a node between x and y:
generate a link between x and node, node and y.

remove node x:
Generate a link from x's prev to future.
*/
struct pll{
    struct node{
        int nxt = 0; // the next node
        bool sat = false;

        int threshold = 0; // must be at least cu to use the second node.
        int onxt = 0;

        int prv = 0; // most recent previous node.
        int id; // id of monk.
    };
    vector<node> a;
    vector<pii> roots;
    // {cu, x}
    set<pii> s; // current set of neighbours
    // {height,id}
    unordered_map<int,int> m; // current location of id
    // id, x.
    node default_node;
    int cu = 0; // current day.
    int cur_root = 0;
    // change when: removing root
    // updating root in gen_link
    // adding a node before the root.
    int gid = 0;
    void init(){
        a.push_back(default_node);
        roots.push_back({0,0});
    }
    void upd_root(int x){
        cur_root = x;
        roots.push_back({cu,x});
        if (gid == 6){
            // printf("%d %d %d\n", cu, x,a[x].id);
            
        }
    }
    void gen_link(int x, int y){
        if (x == 0) return;
        if (a[x].sat){
            int nx = a.size();
            a.push_back(default_node);
            a[nx].nxt = y;
            a[nx].id = a[x].id;
            a[nx].prv = a[x].prv;
            if (y){
                a[y].prv = nx;
            }
            m[a[nx].id] = nx;
            gen_link(a[nx].prv,nx);
            if (cur_root == x){
                upd_root(nx);
            }
        }
        else{
            a[x].sat = true;
            a[x].threshold = cu;
            a[x].onxt = y;
            if (y){
                a[y].prv = x;
            }
        }
    }

    void rem(set<pii>::iterator it,int id){
        int x = m[id];
        int xprev = a[x].prv;
        int xnxt = a[x].sat ? a[x].onxt : a[x].nxt;
        a[xnxt].prv = xprev;
        if (gid == 4){
            // printf("why %d %d %d\n",a[xprev].id, a[xnxt].id, cu);
        }
        if (x== cur_root){
            upd_root(xnxt);
        }
        else{
            gen_link(xprev,xnxt);
        }
        s.erase(it);
    }
    void add(int id){
        int nx = a.size();
        a.push_back(default_node);
        a[nx].id = id;
        m[id] = nx;
        if (s.size() == 0){
            upd_root(nx);
        }
        else{
            auto it = s.lower_bound({h[id],id});
            int prv = 0;
            int aft = 0;
            if (it == s.end()){ // there is nothing after :O

            }
            else{
                aft = m[it -> second];            
            }
            if (it == s.begin()){ // there is nothign before :O
                upd_root(nx);
            }
            else{
                it--;
                prv = m[it -> second];
            }
            a[nx].nxt = aft;
            if (aft) a[aft].prv = nx;
            gen_link(prv,nx);
        }
        s.insert({h[id],id});
    }
    void upd(int tgt, int t){
        cu = t;
        auto it = s.find({h[tgt],tgt});
        if (it != s.end()){
            // time to remove
            rem(it,tgt);
        }
        else{
            add(tgt);
        }
    }
    int do_it(int t, int output){
        int why = 1e9;
        // vector<pii>::iterator it = upper_bound(roots.begin(),roots.end(),make_pair(t,why));
        
        // find rightmost thing <= t
        int lo = 0;
        int hi = roots.size()-1;
        int best = 0;
        while (lo <= hi){
            int mid = (lo + hi)/2;
            if (roots[mid].first <= t){
                best = mid;
                lo = mid+1;
            }
            else{
                hi = mid-1;
            }
        }
        // printf("\nIn %d %d:\n",gid,t);
        // for (pii cur : roots){
        //     printf("%d %d\n", cur.first,cur.second);
        // }
        int x = roots[best].second;
        // printf("%d\n",x);
        int pos = 1;
        // printf("\nAt time %d: %d returns: ",t,gid);
        while (x){
            // printf("%d ",a[x].id);
            ol[output][pos] = h[a[x].id];
            if (a[x].sat && t >= a[x].threshold){
                x = a[x].onxt;
            }
            else{
                x = a[x].nxt;
            }
            pos++;
        }
        // printf("\n");
        return pos-1;
    }
};
pll lists[100005];
// AHHHH what a crazy data structure

inline int dabs(int x){
    return x < 0 ? -x : x;
}


void init(int N, int D, int H[]) {
    n = N;
    for (int i = 1; i <= n; i++){
        h[i] = H[i-1];
        lists[i].init();
        lists[i].gid = i;
    }  
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 0; i < u; i++){
        int b,c;
        b = A[i];
        c = B[i];
        b++;
        c++;
        lists[b].upd(c,i+1);
        lists[c].upd(b,i+1);
    }
}

int question(int x, int y, int v) {
    x++;
    y++;
    int d = v;
    int ans = 1e9;
    int xn = lists[x].do_it(d,0);
    int yn = lists[y].do_it(d,1);

    if (xn != 0){
        if (yn != 0){
            int lo = -1e9;
            int hi = ol[0][1];
            int lpt = 1;
            for (int rpt = 1; rpt <= yn; rpt++){
                while (lpt <  xn && ol[1][rpt] >= hi){
                    lpt++;
                    lo = hi;
                    hi = ol[0][lpt];
                }

                ans = min(ans,ol[1][rpt]-lo);
                ans = min(ans,abs(hi-ol[1][rpt]));
            }
        }
    }
    return ans;
}

Compilation message (stderr)

potion.cpp: In member function 'int pll::do_it(int, int)':
potion.cpp:168:13: warning: unused variable 'why' [-Wunused-variable]
  168 |         int why = 1e9;
      |             ^~~

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