Submission #1043580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043580		jcelin	Radio Towers (IOI22_towers)	C++17	100 / 100	1053 ms	182036 KiB

towers

#pragma once 

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

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = (1 << 30) - 1;
const ll INF = (1ll << 62) - 1;
const int logo = 17;
const int MAXN = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct tour{
	int seg[trsz];
	
	void update(int x, int vl){
		x += off;
		seg[x] = vl;
		for(x /= 2; x; x /= 2) seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
	}
	
	int query(int l, int r){
		int ret = 0;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = max(ret, seg[l++]);
			if(r & 1) ret = max(ret, seg[--r]);
		}
		return ret;
	}
	
	int spusti(int x, int vl, bool fl){
		if(x >= off) return x - off; 
		
		int pr = x * 2;
		if(fl) pr = x * 2 + 1;
		
		if(seg[pr] >= vl) return spusti(pr, vl, fl);
		return spusti(pr ^ 1, vl, fl);
	}
	
	int nadi(int l, int r, int vl, int fl){
		vi lef, rig;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) lef.PB(l++);
			if(r & 1) rig.PB(--r);
		}
		while(rig.size()) lef.PB(rig.back()), rig.PPB();
		
		int ans = 0;
		if(fl == 0){			
			for(auto &x : lef){
				if(ans == 0 and seg[x] >= vl) ans = spusti(x, vl, 0);
			}	
		}else{				
			for(auto it = lef.rbegin(); it != lef.rend(); it++){
				if(ans == 0 and seg[*it] >= vl) ans = spusti(*it, vl, 1);
			}
		}
		
		return ans;
	}
}t;


struct tdelta{
	struct node{
		int v1, v2, ret1, ret2;
		
		node(){
			v1 = inf, v2 = -inf, ret1 = 0, ret2 = 0;
		}
	};
	
	node seg[trsz];
	
	node merge(node a, node b){
		node c;
		c.v1 = min(a.v1, b.v1);
		c.v2 = max(a.v2, b.v2);
		c.ret1 = max(a.ret1, b.ret1);
		c.ret1 = max(c.ret1, b.v2 - a.v1);
		
		c.ret2 = max(a.ret2, b.ret2);
		c.ret2 = max(c.ret2, a.v2 - b.v1);
		return c;
	}
	
	void update(int x, int vl){
		x += off;
		seg[x].v1 = seg[x].v2 = vl;
		for(x /= 2; x; x /= 2) seg[x] = merge(seg[x * 2], seg[x * 2 + 1]);
	}
	
	ii query(int l, int r){
		if(l > r) return {0, 0};
		node ret;
		vi lef, rig;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) lef.PB(l++);
			if(r & 1) rig.PB(--r);
		}
		while(rig.size()) lef.PB(rig.back()), rig.PPB();
		for(auto &x : lef) ret = merge(ret, seg[x]);
		return {ret.ret1, ret.ret2};
	}
	
	int cm ;
	int spusti(int x, int vl){
		if(x >= off) return x - off;
		if(seg[x * 2].ret1 >= vl or seg[x * 2].v2 - cm >= vl) return spusti(x * 2, vl);
		cm = min(cm, seg[x * 2].v1);
		return spusti(x * 2 + 1, vl);
	}
	
	int nadi(int l, int r, int vl){
		vi lef, rig;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) lef.PB(l++);
			if(r & 1) rig.PB(--r);
		}
		while(rig.size()) lef.PB(rig.back()), rig.PPB();
		
		cm = inf;
		int ret = inf;
		for(auto &x : lef){
			if(seg[x].ret1 >= vl or seg[x].v2 - cm >= vl){
				ret = spusti(x, vl);
				return ret;
			}
			cm = min(cm, seg[x].v1);
		}
		return ret;
	}
}del;

bool submit;

struct per{
	struct node{
		node *L, *R;
		int cnt, mi, mx;
		
		node(){
			L = R = 0;
			cnt = mi = mx = 0;
		}
		
		node(node *_L, node *_R, int _cnt, int _mi, int _mx){
			L = _L, R = _R, cnt = _cnt, mi = _mi, mx = _mx;
		}
	};
	
	typedef node* pnode;
	pnode rt[MAXN];
	set<pnode> st;
	
	pnode l(pnode x){return x ? x -> L : 0;}
	pnode r(pnode x){return x ? x -> R : 0;}
	int c(pnode x){return x ? x -> cnt : 0;}
	int sm(pnode x){return x ? x -> mi : 0;}
	int bg(pnode x){return x ? x -> mx : 0;}

	void update(pnode &x, int lo, int hi, int a, int b, int vl){
		if(lo >= b or hi <= a) return;
		if(!submit) st.insert(x);
		x = new node(l(x), r(x), c(x), sm(x), bg(x));
		if(!submit) st.insert(x);
		if(lo >= a and hi <= b){
			if(vl){
				x -> cnt = 1;
				x -> mi = lo;
				x -> mx = lo;
			}else{					
				x -> cnt = 0;
				x -> mi = inf;
				x -> mx = -inf;
			}
			return;
		}	
		int mid = (lo + hi) / 2;
		update(x -> L, lo, mid, a, b, vl);
		update(x -> R, mid, hi, a, b, vl);
		
		x -> mi = min(sm(x -> L), sm(x -> R));
		x -> mx = max(bg(x -> L), bg(x -> R));
		x -> cnt = c(x -> L) + c(x -> R);
	}
	
	int query(pnode &x, int lo, int hi, int a, int b){
		if(lo >= b or hi <= a or !x) return 0;
		if(lo >= a and hi <= b) return c(x);
		int mid = (lo + hi) / 2;
		return query(x -> L, lo, mid, a, b) + query(x -> R, mid, hi, a, b);
	}
	
	ii merge(ii a, ii b){
		return {min(a.X, b.X), max(a.Y, b.Y)};
	}
	
	ii qry(pnode &x, int lo, int hi, int a, int b){
		if(lo >= b or hi <= a or !x) return {inf, -inf};
		if(lo >= a and hi <= b) return {sm(x), bg(x)};
		int mid = (lo + hi) / 2;
		return merge(qry(x -> L, lo, mid, a, b), qry(x -> R, mid, hi, a, b));
	}
	
	void update(int tim, int a, int b, int vl){
		update(rt[tim], 0, off, a, b, vl);
	}
	
	void res(){
		for(auto &x : st) delete x;
		st.clear();
	}
	
	int query(int tim, int l, int r){
		return query(rt[tim], 0, off, l, r);
	}
	
	ii query2(int tim, int l, int r){
		return qry(rt[tim], 0, off, l, r);
	}
}p;


int pm[MAXN], pv[MAXN], vl[MAXN], arr[MAXN];
vii st;
vi upd[MAXN], vals;

void init(int n, vi aa){
	submit = 1;
	for(int i=0; i<n; i++) arr[i + 1] = aa[i];
	st.clear();
	arr[0] = 2 * inf;
	arr[n + 1] = 2 * inf;
	t.update(0, 2 * inf);
	t.update(n + 1, 2 * inf);
	st.PB({-1, -inf});
	for(int i=1; i<=n; i++){
		while(st.back().Y > arr[i]) st.PPB();
		pm[i] = st.back().X;
		st.PB({i, arr[i]});
		t.update(i, arr[i]);
		del.update(i, arr[i]);
	}
	
	st.clear();
	st.PB({n + 2, -inf});
	for(int i=n; i; i--){
		while(st.back().Y > arr[i]) st.PPB();
		pv[i] = st.back().X;
		st.PB({i, arr[i]});
	}
	
	
	for(int i=1; i<=n; i++){
		int a = pm[i], b = pv[i];
		int op = min(t.query(a + 1, i), t.query(i + 1, b));
		op = max(op, arr[i]);
		vl[i] = op - arr[i];
		vals.PB(vl[i]);
	}
	vals.PB(0);
	vals.PB(inf);
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());
	for(int i=1; i<=n; i++){
		vl[i] = lower_bound(all(vals), vl[i]) - vals.begin();
		upd[vl[i] + 1].PB(i);
	}
	
	p.rt[0] = NULL;
	for(int i=1; i<=n; i++) p.update(0, i, i + 1, 1);
	
	for(int i=1; i<(int)vals.size(); i++){
		p.rt[i] = p.rt[i - 1];
		for(auto &x : upd[i]) p.update(i, x, x + 1, 0);
	}
}

int max_towers(int l, int r, int d){
	l++, r++;
	
	auto it = lower_bound(all(vals), d) - vals.begin();
	
	int lef, rig, sum = p.query(it, l, r + 1);
	if(sum == 0){
		if(r - l + 1 >= 3){
			int najl = del.nadi(l, r + 1, d);
			if(del.query(najl, r + 1).Y >= d) return 2;
		}
		return 1;
	}
	tie(lef, rig) = p.query2(it, l, r + 1);
	
	int opt = t.nadi(l, lef, arr[lef] + d, 1);
	if(opt) if(del.query(l, opt + 1).X >= d) sum++;
	
	opt = t.nadi(rig + 1, r + 1, arr[rig] + d, 0);
	if(opt) if(del.query(opt, r + 1).Y >= d) sum++;
	return sum;
}

void zavrsi(){
	p.res();
}

Compilation message (stderr)

towers.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23