oj.uz

Submission #996802

# Submission time Handle Problem Language Result Execution time Memory
996802 2024-06-11T08:51:35 Z Muhammet Radio Towers (IOI22_towers) C++17
0 / 100
 1077 ms 2516 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1077 ms 1644 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '3'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '3'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 448 ms 2516 KB 1st lines differ - on the 1st token, expected: '11903', found: '3'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 856 KB 1st lines differ - on the 1st token, expected: '7197', found: '3'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '3'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1077 ms 1644 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -