oj.uz

Submission #294245

# Submission time Handle Problem Language Result Execution time Memory
294245 2020-09-08T17:59:21 Z TheEpicCowOfLife The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 1756 ms 82076 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19456 KB Output is correct
2 Correct 17 ms 19456 KB Output is correct
3 Correct 15 ms 19456 KB Output is correct
4 Correct 42 ms 26500 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 82040 KB Output is correct
2 Correct 649 ms 81956 KB Output is correct
3 Correct 239 ms 45752 KB Output is correct
4 Correct 1294 ms 63752 KB Output is correct
5 Correct 931 ms 77116 KB Output is correct
6 Correct 1442 ms 56824 KB Output is correct
7 Correct 723 ms 57208 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 82076 KB Output is correct
2 Correct 998 ms 44856 KB Output is correct
3 Correct 1027 ms 57012 KB Output is correct
4 Correct 1537 ms 56824 KB Output is correct
5 Correct 696 ms 81076 KB Output is correct
6 Correct 1569 ms 56732 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 22624 KB Output is correct
2 Correct 76 ms 21208 KB Output is correct
3 Correct 90 ms 20728 KB Output is correct
4 Correct 269 ms 21764 KB Output is correct
5 Correct 263 ms 22264 KB Output is correct
6 Correct 81 ms 22008 KB Output is correct
7 Correct 227 ms 20940 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB Output is correct
2 Correct 17 ms 19456 KB Output is correct
3 Correct 17 ms 19456 KB Output is correct
4 Correct 15 ms 19456 KB Output is correct
5 Correct 42 ms 26500 KB Output is correct
6 Correct 632 ms 82040 KB Output is correct
7 Correct 649 ms 81956 KB Output is correct
8 Correct 239 ms 45752 KB Output is correct
9 Correct 1294 ms 63752 KB Output is correct
10 Correct 931 ms 77116 KB Output is correct
11 Correct 1442 ms 56824 KB Output is correct
12 Correct 723 ms 57208 KB Output is correct
13 Correct 743 ms 82076 KB Output is correct
14 Correct 998 ms 44856 KB Output is correct
15 Correct 1027 ms 57012 KB Output is correct
16 Correct 1537 ms 56824 KB Output is correct
17 Correct 696 ms 81076 KB Output is correct
18 Correct 1569 ms 56732 KB Output is correct
19 Correct 78 ms 22624 KB Output is correct
20 Correct 76 ms 21208 KB Output is correct
21 Correct 90 ms 20728 KB Output is correct
22 Correct 269 ms 21764 KB Output is correct
23 Correct 263 ms 22264 KB Output is correct
24 Correct 81 ms 22008 KB Output is correct
25 Correct 227 ms 20940 KB Output is correct
26 Correct 599 ms 45960 KB Output is correct
27 Correct 1157 ms 56632 KB Output is correct
28 Correct 1213 ms 71100 KB Output is correct
29 Correct 1353 ms 63532 KB Output is correct
30 Correct 1756 ms 56792 KB Output is correct
31 Correct 1347 ms 44836 KB Output is correct
32 Correct 1500 ms 56696 KB Output is correct