oj.uz

Submission #833169

# Submission time Handle Problem Language Result Execution time Memory
833169 2023-08-22T02:44:21 Z pavement Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 2516 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define mp make_pair

using ii = pair<int, int>;

int N;
vector<int> H;

void init(int N, vector<int> H) {
	::N = N;
	::H = H;
}

int max_towers(int L, int R, int D) {
	vector<int> V(H.begin() + L, H.begin() + R + 1), cl(V.size(), -1), cr(V.size(), V.size());
	vector<ii> vec;
	for (int i = 0; i < (int)V.size(); i++) {
		{
			int lo = 0, hi = (int)vec.size() - 1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (vec[mid].first - D >= V[i]) {
					cl[i] = vec[mid].second;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
		}
		while (!vec.empty() && vec.back().first <= V[i]) {
			vec.pop_back();
		}
		vec.eb(V[i], i);
	}
	vec.clear();
	for (int i = (int)V.size() - 1; i >= 0; i--) {
		{
			int lo = 0, hi = (int)vec.size() - 1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (vec[mid].first - D >= V[i]) {
					cr[i] = vec[mid].second;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
		}
		while (!vec.empty() && vec.back().first <= V[i]) {
			vec.pop_back();
		}
		vec.eb(V[i], i);
	}
	//~ for (int i : V) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	//~ for (int i : cl) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	//~ for (int i : cr) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	function<int(int, int, bool, bool)> solve = [&](int l, int r, bool a = 0, bool b = 0) {
		if (l > r) {
			return 0;
		}
		ii to = mp((int)2e9, -1);
		for (int i = l; i <= r; i++) {
			if ((!a || l <= cl[i]) && (!b || cr[i] <= r)) {
				to = min(to, mp(V[i], i));
			}
		}
		if (to.second != -1) {
			return solve(l, to.second - 1, a, 1) + solve(to.second + 1, r, 1, b) + 1;
		} else {
			return 0;
		}
	};
	return solve(0, (int)V.size() - 1, 0, 0);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 2516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 2240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4006 ms 848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 2516 KB Time limit exceeded
2 Halted 0 ms 0 KB -