oj.uz

Submission #832532

# Submission time Handle Problem Language Result Execution time Memory
832532 2023-08-21T11:14:54 Z NothingXD Radio Towers (IOI22_towers) C++17
4 / 100
 2183 ms 8780 KB 
#include "towers.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}
 
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;
const int lg = 20;

int n, x, h[maxn], mx[lg][maxn], l[maxn], r[maxn], f[2][maxn];

void add(int *f, int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

void add(int *f, int l, int r, int x){
	add(f, l, x);
	add(f, r+1, -x);
}

int get(int *f, int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

int get(int *f, int l, int r){
	if (r < l) return 0;
	return get(f, r) - get(f, l-1);
}

int getmax(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	return max(mx[x][l], mx[x][r-(1 << x)]);
}

void init(int N, std::vector<int> H) {
	n = N;
	for (int i = 0; i < n; i++){
		h[i] = H[i];
		mx[0][i] = h[i];
	}
	for (int i = 1; i < lg; i++){
		for (int j = 0; j + (1 << i) <= n; j++){
			mx[i][j] = max(mx[i-1][j], mx[i-1][j+(1<<(i-1))]);
		}
	}
	for (int i = 1; i + 1 < n; i++){
		if (h[i-1] < h[i] && h[i] > h[i+1]) x = i;
	}
}

int max_towers(int L, int R, int D) {
	memset(f, 0, sizeof f);
	vector<int> tmp = {L, R};
	if (L < x && x < R) tmp.push_back(x);
	for (auto i: tmp){
		int lo = L, hi = i;
		while(lo + 1 < hi){
			int mid = (lo + hi) >> 1;
			if (getmax(mid, i-1) - D >= h[i]) lo = mid;
			else hi = mid;
		}
		l[i] = lo;
	}
	vector<pii> val;
	for (auto i: tmp){
		int lo = i, hi = R;
		while(lo + 1 < hi){
			int mid = (lo + hi) >> 1;
			if (getmax(i+1, mid) - D >= h[i]) hi = mid;
			else lo = mid;
		}
		r[i] = hi;
		val.push_back({h[i], i});
	}

	sort(all(val));

	int ans = 0;

	for (auto [x, y]: val){
		if (get(f[0], y+1)) continue;
		if (get(f[1], l[y]+1, r[y]+1)) continue;
		ans++;
		add(f[0], l[y]+1, r[y]+1, 1);
		add(f[1], y+1, 1);
	}
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 5508 KB Output is correct
2 Correct 2135 ms 8780 KB Output is correct
3 Correct 2071 ms 8752 KB Output is correct
4 Correct 2183 ms 8768 KB Output is correct
5 Correct 2039 ms 8780 KB Output is correct
6 Correct 2128 ms 8764 KB Output is correct
7 Correct 2069 ms 8768 KB Output is correct
8 Correct 1 ms 1104 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 5508 KB Output is correct
2 Correct 2135 ms 8780 KB Output is correct
3 Correct 2071 ms 8752 KB Output is correct
4 Correct 2183 ms 8768 KB Output is correct
5 Correct 2039 ms 8780 KB Output is correct
6 Correct 2128 ms 8764 KB Output is correct
7 Correct 2069 ms 8768 KB Output is correct
8 Correct 1 ms 1104 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 1 ms 1232 KB Output is correct
11 Incorrect 1 ms 1104 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
12 Halted 0 ms 0 KB -