Submission #631857

#	Time	Username	Problem	Language	Result	Execution time	Memory
631857		TheLostCookie	Radio Towers (IOI22_towers)	C++17	100 / 100	1588 ms	98728 KiB

towers

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

const int INF = 2e9;

#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define ROF(i,a,b) for(int i=(b)-1; i>=(a); --i)

typedef vector<int> vi;
typedef pair<int,int> ii;

struct SegmentTree {
	int v;
	int N;
	int minH,maxH;
	SegmentTree* left;
	SegmentTree* right;
	
	SegmentTree(SegmentTree* st) {
		v = st->v;
		N = st->N;
		minH = st->minH;
		maxH = st->maxH;
		left = st->left;
		right = st->right;
	}
	
	SegmentTree(int l, int r, vi &init, vi &H) {
		if(r-l==1) {
			left = right = nullptr;
			v = init[l];
			minH = maxH = H[l];
			N = H.size();
		} else {
			int m = (l+r)/2;
			left = new SegmentTree(l,m,init,H);
			right = new SegmentTree(m,r,init,H);
			pull();
		}
	}
	
	SegmentTree* modify(int p, int l, int r, int val) {
		if(l == r) return nullptr;
		SegmentTree* st = new SegmentTree(this);
		if(r-l == 1) {
			st->v += val;
		} else {
			int m = (l+r)/2;
			if(p < m) st->left = left->modify(p,l,m,val);
			else st->right = right->modify(p,m,r,val);
			st->pull();
		}
		return st;
	}
	
	SegmentTree* modify(int p, int val) {
		return modify(p,0,N,val);
	}
	
	int rangeQuerySum(int l, int r, int _l, int _r) {
		if(l >= _r || _l >= r) {
			return 0;
		} else if(_l <= l && r <= _r) {
			return v;
		} else {
			int m = (l+r)/2;
			int lq = left->rangeQuerySum(l,m,_l,_r);
			int rq = right->rangeQuerySum(m,r,_l,_r);
			return lq+rq;
		}
	}
	
	int rangeQuerySum(int l, int r) {
		return rangeQuerySum(0,N,l,r);
	}
	
	int rangeQueryMinHeight(int l, int r, int _l, int _r) {
		if(l >= _r || _l >= r) {
			return INF;
		} else if(_l <= l && r <= _r) {
			return minH;
		} else {
			int m = (l+r)/2;
			int lq = left->rangeQueryMinHeight(l,m,_l,_r);
			int rq = right->rangeQueryMinHeight(m,r,_l,_r);
			return min(lq,rq);
		}
	}
	
	int rangeQueryMinHeight(int l, int r) {
		return rangeQueryMinHeight(0,N,l,r);
	}
	
	int findFirst(int l, int r, int _l, int _r) {
		if(v==0 || l >= _r || _l >= r) {
			return -1;
		} else if(r-l==1) {
			return l;
		} else {
			int m = (l+r)/2;
			int ans = left->findFirst(l,m,_l,_r);
			if(ans == -1) return right->findFirst(m,r,_l,_r);
			else return ans;
		}
	}
	
	int findFirst(int l, int r) {
		return findFirst(0,N,l,r);
	}
	
	int findLast(int l, int r, int _l, int _r) {
		if(v==0 || l >= _r || _l >= r) {
			return -1;
		} else if(r-l==1) {
			return l;
		} else {
			int m = (l+r)/2;
			int ans = right->findLast(m,r,_l,_r);
			if(ans == -1) return left->findLast(l,m,_l,_r);
			else return ans;
		}
	}
	
	int findLast(int l, int r) {
		return findLast(0,N,l,r);
	}
	
	void pull() {
		N = left->N;
		v = left->v + right->v;
		minH = min(left->minH,right->minH);
		maxH = max(left->maxH,right->maxH);
	}
};

map<int,SegmentTree*> mp;
vector<int> heights;

void init(int N, std::vector<int> H) {
	heights = H;
	vi init(N,0);
	FOR(i,0,N) {
		if(i == 0 || i == N-1 || H[i] > max(H[i-1],H[i+1]) || H[i] < min(H[i-1],H[i+1])) {
			init[i] = 1;
		}
	}
	priority_queue<pair<int,ii>,vector<pair<int,ii>>,greater<pair<int,ii>>> pq;
	int prvH = -1, prvArg = -1;
	FOR(i,0,N) {
		if(init[i] == 1) {
			if(prvH != -1) {
				pq.push({abs(prvH-H[i]),{prvArg,i}});
			}
			prvH = H[i];
			prvArg = i;
		}
	}
	
	SegmentTree* st = new SegmentTree(0,N,init,H);
	mp[1] = st;
	
	while(!pq.empty()) {
		auto [d,v] = pq.top(); pq.pop();
		auto [i,j] = v;
		if(st->findFirst(i,i+1) == i && st->findFirst(j,j+1) == j) {
			int prv = st->findLast(0,i);
			int nxt = st->findFirst(j+1,N);
			if(prv != -1 && nxt != -1) {
				st = st->modify(i,-1);
				st = st->modify(j,-1);
				pq.push({abs(H[prv]-H[nxt]),{prv,nxt}});
			} else if(nxt != -1) {
				st = st->modify(i,-1);
			} else {
				st = st->modify(j,-1);
			}
			mp[d+1] = st;
		}
		
	}
	assert(st->findFirst(0,N) == st->findLast(0,N));
	return;
}

int max_towers(int L, int R, int D) {
	SegmentTree* st = prev(mp.upper_bound(D))->second;
	int ans = st->rangeQuerySum(L,R+1);
	if(ans == 0) return 1;
	else if(ans == 1) {
		int tow = st->findFirst(L,R+1);
		assert(tow == st->findLast(L,R+1));
		int prefMin = st->rangeQueryMinHeight(L,tow);
		if(prefMin <= heights[tow] - D) ans++;
		int suffMin = st->rangeQueryMinHeight(tow+1,R+1);
		if(suffMin <= heights[tow] - D) ans++;
		return (ans+1)/2;
	} else {
		int fi1 = st->findFirst(L,R+1);
		int fi2 = st->findFirst(fi1+1,R+1);
		int la1 = st->findLast(L,R+1);
		int la2 = st->findLast(L,la1);
		
		if(heights[fi1] > heights[fi2]) {
			int prefMin = st->rangeQueryMinHeight(L,fi1);
			if(prefMin <= heights[fi1] - D) ans++;
			else ans--;
		}
		if(heights[la1] > heights[la2]) {
			int suffMin = st->rangeQueryMinHeight(la1+1,R+1);
			if(suffMin <= heights[la1] - D) ans++;
			else ans--;
		}
		assert(ans%2 == 1);
		return (ans+1)/2;
	}
 
	return 0;
}

• 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