oj.uz

답안 #631763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631763 2022-08-18T17:07:24 Z TheLostCookie 송신탑 (IOI22_towers) C++17
11 / 100
 4000 ms 46596 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 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);
	}
};

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();
	
	while(!pq.empty()) {
		auto [d,v] = pq.top(); pq.pop();
		auto [i,j] = v;
		if(segTrees.back()->findFirst(i,i+1) == i && segTrees.back()->findFirst(j,j+1) == j) {
			int prv = segTrees.back()->findLast(0,i);
			int nxt = segTrees.back()->findFirst(j+1,N);
			if(prv != -1 && nxt != -1) {
				SegmentTree* st = segTrees.back()->modify(i,-1);
				segTrees.push_back(st->modify(j,-1));
				pq.push({abs(H[prv]-H[nxt]),{prv,nxt}});
			} else if(nxt != -1) {
				SegmentTree* st = segTrees.back();
				segTrees.push_back(st->modify(i,-1));
			} else {
				SegmentTree* st = segTrees.back();
				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 = 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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4069 ms 14892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 5 ms 1360 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 6 ms 1744 KB Output is correct
6 Correct 6 ms 1744 KB Output is correct
7 Correct 6 ms 1744 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 4 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 3 ms 580 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 7 ms 1744 KB Output is correct
18 Correct 4 ms 592 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 5 ms 1360 KB Output is correct
21 Correct 6 ms 1744 KB Output is correct
22 Correct 5 ms 1744 KB Output is correct
23 Correct 3 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 6 ms 1744 KB Output is correct
29 Correct 6 ms 1832 KB Output is correct
30 Correct 6 ms 1744 KB Output is correct
31 Correct 7 ms 1744 KB Output is correct
32 Correct 4 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 5 ms 1360 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 6 ms 1744 KB Output is correct
6 Correct 6 ms 1744 KB Output is correct
7 Correct 6 ms 1744 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 4 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 3 ms 580 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 7 ms 1744 KB Output is correct
18 Correct 4 ms 592 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 5 ms 1360 KB Output is correct
21 Correct 6 ms 1744 KB Output is correct
22 Correct 5 ms 1744 KB Output is correct
23 Correct 3 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 6 ms 1744 KB Output is correct
29 Correct 6 ms 1832 KB Output is correct
30 Correct 6 ms 1744 KB Output is correct
31 Correct 7 ms 1744 KB Output is correct
32 Correct 4 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 3101 ms 46596 KB Output is correct
37 Execution timed out 4070 ms 22512 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4041 ms 22908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 796 ms 16472 KB Output is correct
2 Execution timed out 4049 ms 23220 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1360 KB Output is correct
3 Correct 5 ms 1360 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 6 ms 1744 KB Output is correct
6 Correct 6 ms 1744 KB Output is correct
7 Correct 6 ms 1744 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 4 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 3 ms 580 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 7 ms 1744 KB Output is correct
18 Correct 4 ms 592 KB Output is correct
19 Correct 4 ms 592 KB Output is correct
20 Correct 5 ms 1360 KB Output is correct
21 Correct 6 ms 1744 KB Output is correct
22 Correct 5 ms 1744 KB Output is correct
23 Correct 3 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 6 ms 1744 KB Output is correct
29 Correct 6 ms 1832 KB Output is correct
30 Correct 6 ms 1744 KB Output is correct
31 Correct 7 ms 1744 KB Output is correct
32 Correct 4 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 3101 ms 46596 KB Output is correct
37 Execution timed out 4070 ms 22512 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4069 ms 14892 KB Time limit exceeded
2 Halted 0 ms 0 KB -