Submission #996802

#	Time	Username	Problem	Language	Result	Execution time	Memory
996802		Muhammet	송신탑 (IOI22_towers)	C++17	0 / 100	1077 ms	2516 KiB

towers

#include <bits/stdc++.h>

#define N 200005
#define ll long long
#define sz(s) (int)s.size()
#define ff first
#define ss second

using namespace std;

ll n;

bool tr = 0;

vector <int> h;

vector <pair<int,int>> a;

void init(int N1, vector<int> H){
	n = N1;
	h = H;
	return;
}

int max_towers(int l, int r, int d){
	if(tr == 0){
		tr = 1;
		a.clear();
		for(int i = 0; i < n; i++) a.push_back({-1,n});
		vector <int> v;
		for(int i = 0; i < n; i++){
			while(sz(v) > 0 and h[v.back()] >= h[i]){
				v.pop_back();
			}
			int l1 = 0, r1 = sz(v)-1, k = -1;
			while(l1 <= r1){
				int md = (l1+r1) / 2;
				if(h[v[md]] <= h[i]-d){
					l1 = md+1;
					k = md;
				}
				else {
					r1 = md-1;
				}
			}
			if(k != -1){
				a[i].ff = v[k];
			}
			v.push_back(i);
		}
		v.clear();
		for(int i = n-1; i >= 0; i--){
			while(sz(v) > 0 and h[v.back()] >= h[i]){
				v.pop_back();
			}
			int l1 = 0, r1 = sz(v)-1, k = -1;
			while(l1 <= r1){
				int md = (l1+r1) / 2;
				if(h[v[md]] <= h[i]-d){
					l1 = md+1;
					k = md;
				}
				else {
					r1 = md-1;
				}
			}
			if(k != -1){
				a[i].ss = v[k];
			}
			v.push_back(i);
		}
	}
	int x = 2;
	x = min(x,(r-l+1));
	for(int i = l; i <= r; i++){
		if(a[i].ff >= l and a[i].ss <= r){
			x = 3;
			break;
		}
	}
	return x;
}

• Subtask 1: 0 / 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