Submission #627340

#	Time	Username	Problem	Language	Result	Execution time	Memory
627340		minhcool	Radio Towers (IOI22_towers)	C++17	4 / 100	861 ms	19604 KiB

towers

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

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

const int oo = 1e9 + 7, mod = 1e9 + 7;

int n, a[N];

int ind_mx = 1;

bool sub1 = 0;

void init(int _n, vector<int> _a){
	n = _n;
	for(int i = 0; i < n; i++) a[i + 1] = _a[i];
	for(int i = 2; i <= n; i++) if(a[i] > a[ind_mx]) ind_mx = i;
	sub1 = 1;
	for(int i = 1; i < ind_mx; i++) sub1 &= (a[i + 1] > a[i]);
	for(int i = ind_mx; i < n; i++) sub1 &= (a[i] > a[i + 1]);
}

int dp[N], lstl[N], lstr[N];

int mx[N][20], lg2[20];

int maxi(int l, int r){
	if(l > r) return 0;
	int k = lg2[r - l + 1];
	return max(mx[l][k], mx[r - (1LL << k) + 1][k]);
}

int IT[N << 2];

void upd(int id, int l, int r, int pos, int val){
	IT[id] = max(IT[id], val);
	if(l == r){
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upd(id << 1, l, mid, pos, val);
	else upd(id << 1 | 1, mid + 1, r, pos, val);
}

int get(int id, int l, int r, int L, int R){
	if(l > R || r < L || L > R) return 0;
	if(l >= L && r <= R) return IT[id];
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}

int max_towers(int l, int r, int d){
	l++, r++;
	if(sub1){
		if(r <= ind_mx || l >= ind_mx) return 1;
		else if(max(a[l], a[r]) > (a[ind_mx] - d)) return 1;
		else return 2;
	}
	else if(n <= 000){
		for(int i = l; i <= r; i++){
			lstl[i] = -oo, lstr[i] = oo;
			for(int j = i + 1; j <= r; j++){
				if(a[j] >= (a[i] + d)){
					lstr[i] = j;
					break;
				}
			}
			for(int j = i - 1; j >= l; j--){
				if(a[j] >= (a[i] + d)){
					lstl[i] = j;
					break;
				}
			}
			//cout << lstl[i] << " " << lstr[i] << "\n";
		}
		int mx = -1;
		for(int i = l; i <= r; i++){
			dp[i] = 0;
			for(int j = l; j <= i - 1; j++){
				if(lstl[i] < lstr[j]) continue;
				//cout << i << " " << j << "\n";
				dp[i] = max(dp[i], dp[j]);
			}
			dp[i]++;
			mx = max(mx, dp[i]);
		}
		return mx;
	}
	else{
		for(int i = l; i <= r; i++) mx[i][0] = a[i];
		for(int i = 1; i <= 19; i++){
			for(int j = l; j <= (r - (1LL << i) + 1); j++){
				mx[j][i] = max(mx[j][i - 1], mx[j + (1LL << (i - 1))][i - 1]);
			}
		}
		for(int i = l; i <= r; i++){
			if(maxi(i + 1, r) < (a[i] + d)) lstr[i] = oo;
			else{
				lstr[i] = i;
				for(int j = 19; j >= 0; j--){
					if(lstr[i] + (1LL << j) > r) continue;
					if(mx[lstr[i]][j] < (a[i] + d)){
						lstr[i] += (1LL << j);
						//cout << i << " " << j << "\n";
					}
				}
				//lstr[i]++;
			}
			if(maxi(l, i - 1) < (a[i] + d)) lstl[i] = -oo;
			else{
				lstl[i] = i;
				for(int j = 19; j >= 0; j--){
					if(lstl[i] - (1LL << j) < l) continue;
					if(mx[lstl[i] - (1LL << j) + 1][j] < (a[i] + d)) lstl[i] -= (1LL << j);
				}
				//lstl[i]--;
			}
			//cout << i << " " << lstl[i] << " " << lstr[i] << "\n";
		}
		int mx = -1;
		for(int i = 1; i <= (n << 2); i++) IT[i] = 0;
		for(int i = l; i <= r; i++){
			dp[i] = get(1, 1, n + 1, l, max(lstl[i], l - 1)) + 1;
			upd(1, 1, n + 1, min(r + 1, lstr[i]), dp[i]);
			mx = max(mx, dp[i]);
			//cout << i << " " << dp[i] << "\n";
		}
		return mx;
	}
}

/*
void process(){
	int n, q;
	vector<int> a;
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		a.pb(x);
	}
	init(n, a);
	while(q--){
		int l, r, d;
		cin >> l >> r >> d;
		cout << max_towers(l, r, d) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}
*/

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