oj.uz

Submission #631769

# Submission time Handle Problem Language Result Execution time Memory
631769 2022-08-18T17:25:16 Z TheLostCookie Radio Towers (IOI22_towers) C++17
11 / 100
 4000 ms 46784 KB 
#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 N;
	int v;
	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);
	}

	tuple<int,int,int> rangeQuery(int l, int r, int _l, int _r) {
		if(l >= _r || _l >= r) {
			return make_tuple(0,INF,-INF);
		} else if(_l <= l && r <= _r) {
			return make_tuple(v,minH,maxH);
		} else {
			int m = (l+r)/2;
			tuple<int,int,int> lq = left->rangeQuery(l,m,_l,_r);
			tuple<int,int,int> rq = right->rangeQuery(m,r,_l,_r);
			return make_tuple(get<0>(lq)+get<0>(rq),min(get<1>(lq),get<1>(rq)),max(get<2>(lq),get<2>(rq)));
		}
	}

	tuple<int,int,int> rangeQuery(int l, int r) {
		return rangeQuery(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);
	}
};

vector<SegmentTree*> segTrees;
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;
		}
	}

	segTrees.push_back(new SegmentTree(0,N,init,H));
	mp[1] = segTrees.back();

	set<int> keyTowers;
	FOR(i,0,N) if(init[i] == 1) keyTowers.insert(i);
	keyTowers.insert(-1), keyTowers.insert(N+1);
	while(!pq.empty()) {
		auto [d,v] = pq.top(); pq.pop();
		auto [i,j] = v;
		if(keyTowers.count(i) && keyTowers.count(j)) {
			int prv = *prev(keyTowers.find(i));
			int nxt = *keyTowers.upper_bound(j);
			if(prv != -1 && nxt != N+1) {
				SegmentTree* st = segTrees.back()->modify(i,-1);
				segTrees.push_back(st->modify(j,-1));
				
				keyTowers.erase(i);
				keyTowers.erase(j);
				
				pq.push({abs(H[prv]-H[nxt]),{prv,nxt}});
			} else if(nxt != N+1) {
				SegmentTree* st = segTrees.back();
				
				keyTowers.erase(i);
				
				segTrees.push_back(st->modify(i,-1));
			} else {
				SegmentTree* st = segTrees.back();
				
				keyTowers.erase(j);
				
				segTrees.push_back(st->modify(j,-1));
			}
		}
		
		mp[d+1] = segTrees.back();
	}
	assert(segTrees.back()->findFirst(0,N) == segTrees.back()->findLast(0,N));
	return;
}

int max_towers(int L, int R, int D) {
	SegmentTree* st = prev(mp.upper_bound(D))->second;
	int ans = get<0>(st->rangeQuery(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 = get<1>(st->rangeQuery(L,tow));
		if(prefMin <= heights[tow] - D) ans++;
		int suffMin = get<1>(st->rangeQuery(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 = get<1>(st->rangeQuery(L,fi1));
			if(prefMin <= heights[fi1] - D) ans++;
			else ans--;
		}
		if(heights[la1] > heights[la2]) {
			int suffMin = get<1>(st->rangeQuery(la1+1,R+1));
			if(suffMin <= heights[la1] - D) ans++;
			else ans--;
		}
		assert(ans%2 == 1);
		return (ans+1)/2;
	}

	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4051 ms 14724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 7 ms 1360 KB Output is correct
4 Correct 6 ms 1744 KB Output is correct
5 Correct 7 ms 1744 KB Output is correct
6 Correct 17 ms 1828 KB Output is correct
7 Correct 7 ms 1748 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 592 KB Output is correct
15 Correct 5 ms 1360 KB Output is correct
16 Correct 6 ms 1744 KB Output is correct
17 Correct 6 ms 1852 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 4 ms 636 KB Output is correct
20 Correct 5 ms 1360 KB Output is correct
21 Correct 6 ms 1744 KB Output is correct
22 Correct 7 ms 1848 KB Output is correct
23 Correct 5 ms 592 KB Output is correct
24 Correct 3 ms 592 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 5 ms 1360 KB Output is correct
27 Correct 5 ms 1360 KB Output is correct
28 Correct 7 ms 1744 KB Output is correct
29 Correct 6 ms 1744 KB Output is correct
30 Correct 6 ms 1744 KB Output is correct
31 Correct 7 ms 1744 KB Output is correct
32 Correct 3 ms 592 KB Output is correct
33 Correct 4 ms 592 KB Output is correct
34 Correct 3 ms 592 KB Output is correct
35 Correct 3 ms 592 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 7 ms 1360 KB Output is correct
4 Correct 6 ms 1744 KB Output is correct
5 Correct 7 ms 1744 KB Output is correct
6 Correct 17 ms 1828 KB Output is correct
7 Correct 7 ms 1748 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 592 KB Output is correct
15 Correct 5 ms 1360 KB Output is correct
16 Correct 6 ms 1744 KB Output is correct
17 Correct 6 ms 1852 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 4 ms 636 KB Output is correct
20 Correct 5 ms 1360 KB Output is correct
21 Correct 6 ms 1744 KB Output is correct
22 Correct 7 ms 1848 KB Output is correct
23 Correct 5 ms 592 KB Output is correct
24 Correct 3 ms 592 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 5 ms 1360 KB Output is correct
27 Correct 5 ms 1360 KB Output is correct
28 Correct 7 ms 1744 KB Output is correct
29 Correct 6 ms 1744 KB Output is correct
30 Correct 6 ms 1744 KB Output is correct
31 Correct 7 ms 1744 KB Output is correct
32 Correct 3 ms 592 KB Output is correct
33 Correct 4 ms 592 KB Output is correct
34 Correct 3 ms 592 KB Output is correct
35 Correct 3 ms 592 KB Output is correct
36 Correct 3223 ms 46784 KB Output is correct
37 Execution timed out 4054 ms 22560 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4025 ms 22900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 16452 KB Output is correct
2 Execution timed out 4049 ms 23436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 7 ms 1360 KB Output is correct
4 Correct 6 ms 1744 KB Output is correct
5 Correct 7 ms 1744 KB Output is correct
6 Correct 17 ms 1828 KB Output is correct
7 Correct 7 ms 1748 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 592 KB Output is correct
15 Correct 5 ms 1360 KB Output is correct
16 Correct 6 ms 1744 KB Output is correct
17 Correct 6 ms 1852 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 4 ms 636 KB Output is correct
20 Correct 5 ms 1360 KB Output is correct
21 Correct 6 ms 1744 KB Output is correct
22 Correct 7 ms 1848 KB Output is correct
23 Correct 5 ms 592 KB Output is correct
24 Correct 3 ms 592 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 5 ms 1360 KB Output is correct
27 Correct 5 ms 1360 KB Output is correct
28 Correct 7 ms 1744 KB Output is correct
29 Correct 6 ms 1744 KB Output is correct
30 Correct 6 ms 1744 KB Output is correct
31 Correct 7 ms 1744 KB Output is correct
32 Correct 3 ms 592 KB Output is correct
33 Correct 4 ms 592 KB Output is correct
34 Correct 3 ms 592 KB Output is correct
35 Correct 3 ms 592 KB Output is correct
36 Correct 3223 ms 46784 KB Output is correct
37 Execution timed out 4054 ms 22560 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4051 ms 14724 KB Time limit exceeded
2 Halted 0 ms 0 KB -