#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);
lists[c].upd(b,i);
}
}
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19192 KB |
Incorrect |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19456 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
470 ms |
153044 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
582 ms |
75684 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
22144 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19192 KB |
Incorrect |
