Submission #1209764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209764		dio_2	송신탑 (IOI22_towers)	C++20	27 / 100	355 ms	42876 KiB

towers

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

// Observation 1: For every 2 towers we pick (i, j) |i - j| > 1 -> this means they cannot be adjacent.
// Observation 2: Can(a, b) ^ Can(b, c) => Can(a, c)   (so you only care if adjacent pairs can)
// Observation 3: The heights of all towers are distinct! (first time I read that).
// Observation 4: Because of (Obs2) we can use dp for computing answer -> dp[i] -> max tower sequence such that it ends in tower i.

int subtask1 = 0;
int subtask2 = 0;
int n;
int point_k;
int h[1000000];
int que = 0;
// might need clearing not sure
map<int, int> comp;
int uncomp[4000000];

struct MaxSegTree{
	int base;
	std::vector<int> tree;
	const int neutral = 0;
	MaxSegTree (int n){
		base = 1;
		while(base <= n) base *= 2;
		tree.assign(2 * base, neutral);
	}
	
	void update(int node, int lx, int rx, int pos, int val){
		if(lx == rx){
			tree[node] = max(tree[node], val);
			return ;
		}
		int mid = (lx + rx) / 2;
		if(pos <= mid)
			update(2 * node, lx, mid, pos, val);
		else 
			update(2 * node + 1, mid + 1, rx, pos, val);
		tree[node] = max(tree[2 * node], tree[2 * node + 1]);
	}
	
	void update(int pos, int val){
		update(1, 1, base, pos, val);
	}
	
	int get_max(int node, int lx, int rx, int l, int r){
		if(l > rx || r < lx) return neutral;
		if(l <= lx && rx <= r) return tree[node];
		int mid = (lx + rx) / 2;
		return max( get_max(2 * node, lx, mid, l, r), 
							  get_max(2 * node + 1, mid + 1, rx, l, r) );
	}
	
	int get_max(int l, int r){
		return get_max(1, 1, base, l, r);
	}
	
};

void is1(int N, std::vector<int> H){
	std::vector<int> isDec(N);    // it should be decreasing to the right
																// so it should be increasing if we look at it from right.
	isDec[N - 1] = 1;
	for(int i = N - 2;i >= 0;i--){
		isDec[i] = (isDec[i + 1] & (H[i] > H[i + 1]));
	}
	
	int inc = 1;
	point_k = 0;
	for(int i = 0;i < N;i++){
		if(H[i] == H[i - 1]) break;
		if(i > 0) inc &= (H[i] > H[i - 1]);
		if(isDec[i] && inc){
			subtask1 = 1;
			point_k = i;
		}
	}
}

int do1(int L, int R, int D){
	if(!(L <= point_k && point_k <= R)) return 1;
	if(L == point_k || R == point_k) return 1;
	return (h[L] <= h[point_k] - D && h[R] <= h[point_k] - D) ? 2 : 1;
}

void is2(int N){
	subtask2 |= (N <= 2000);
}

int do2(int L, int R, int D){
	int ans = 1;
	// dp[i] -> max tower sequence ending at i
	// i H[i]
	
	std::vector<int> dp(n);
	dp[L] = 1;
	for(int i = L + 1;i <= R;i++){
		dp[i] = 1;
		int mx = h[i - 1] - D;
		for(int j = i - 2;j >= 0;j--){
			if(h[i] <= mx && h[j] <= mx) dp[i] = max(dp[i], dp[j] + 1);
			mx = max(mx, h[j] - D);
		}
		ans = max(ans, dp[i]);
	}
	return ans;
}

int cnt;
void compress(int D){
	std::set<int> s;
	for(int i = 0;i < n;i++){
		s.insert(h[i]);
		s.insert(h[i] + D);
		s.insert(h[i] - D);
	}
	cnt = 0;
	for(int x : s){
		comp[x] = ++cnt;
		uncomp[cnt] = x;
	}
}

int do3(int L, int R, int D){ // N <= 10^5
	compress(D);
	std::vector<MaxSegTree> dp(2, MaxSegTree(4 * n));
	// dp[0][i] => max and i am in the middle.
	// dp[1][i] => max but i have ended.
	dp[1].update(comp[h[L]], 1);
	for(int i = L + 1;i <= R;i++){
		dp[1].update(comp[h[i]], 1);
		dp[1].update(comp[h[i]], 1 + dp[0].get_max(comp[h[i] + D], 4 * n));
		dp[0].update(comp[h[i]], dp[1].get_max(0, comp[h[i] - D]));
	}
	
	return dp[1].tree[1];
}

int do4(int L, int R, int D){
	assert(D == 1); // ligo paromoio me D is constant.
	/*
	
	for a triple (i, k, j)
	a[i] <= a[k] - 1  => a[i] < a[k]
	a[j] <= a[k] - 1  => a[j] < a[k]
	equal values are annoying
	but after removing them we have something like
	small big small big small big small
	answer is of course small count
	but we have to be smart
	
	*/
		
		return 1;
}

int do5(int D){ // cause L = 0, R = n - 1
	return 1;
}

void init(int N, std::vector<int> H){	
	is1(N, H);
	is2(N);
	que = 0;
	// removed point_k = 0
	n = N;
	for(int i = 0;i < n;i++){
		h[i] = H[i];
	}
}

int max_towers(int L, int R, int D){
	if(subtask1){										 	// we have a mountain.
		return do1(L, R, D);
	}
	que++;
	if(subtask2){
		return do2(L, R, D);
	}
	if(que == 1){
		return do3(L, R, D);
	}
	assert(false);
	return 1;
}

const bool testing = true;

//~ int main(){
	//~ if(testing){
		//~ n = 7;
		//~ h[0]=10;
		//~ h[1]=20;
		//~ h[2]=60;
		//~ h[3]=40;
		//~ h[4]=50;
		//~ h[5]=30;
		//~ h[6]=70;
		//~ cerr << "do3(1, 5, 10): " << do3(1, 5, 10) << endl;
		//~ cerr << "do3(2, 5, 10): " << do3(2, 5, 10) << endl;
		//~ cerr << "do3(3, 5, 10): " << do3(3, 5, 10) << endl;
	//~ }
	//~ return 0;
//~ }	

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