oj.uz

Submission #987802

# Submission time Handle Problem Language Result Execution time Memory
987802 2024-05-23T15:34:39 Z siewjh Radio Towers (IOI22_towers) C++17
0 / 100
 1104 ms 124356 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct node{
	int s, m, e, val;
	node *l, *r;
	node(int _s, int _e, vector<int> &arr){
		s = _s, e = _e, m = (s + e) >> 1;
		if (s == e) val = arr[s];
		else{
			l = new node(s, m, arr); r = new node(m + 1, e, arr);
			val = max(l->val, r->val);
		}
	}
	int query(int x, int y){
		if (x > y) return -1;
		if (x == s && y == e) return val;
		else if (y <= m) return l->query(x, y);
		else if (x > m) return r->query(x, y);
		else return max(l->query(x, m), r->query(m + 1, y));
	}
};
struct node2{
	int s, m, e, val;
	node2 *l = nullptr, *r = nullptr;
	node2 (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1, val = 0;
		if (s != e){
			l = new node2(s, m); r = new node2(m + 1, e);
		}
	}
	node2 (node2 *x){
		s = x->s, e = x->e, m = x->m, val = x->val;
		l = x->l; r = x->r;
	}
	void update(int p, int v){
		val += v;
		if (s == e) return;
		else if (p <= m){
			l = new node2(l); l->update(p, v);
		}
		else{
			r = new node2(r); r->update(p, v);
		}
	}
	int cnt(int x, int y){
		if (x == s && y == e) return val;
		else if (y <= m) return l->cnt(x, y);
		else if (x > m) return r->cnt(x, y);
		else return l->cnt(x, m) + r->cnt(m + 1, y);
	}
	int lf(int x, int y){
		if (val == 0) return -1;
		if (s == e) return s;
		else if (y <= m) return l->lf(x, y);
		else if (x > m) return r->lf(x, y);
		else{
			int v = l->lf(x, m);
			return (v != -1 ? v : r->lf(m + 1, y));
		}
	}
	int rf(int x, int y){
		if (val == 0) return -1;
		if (s == e) return s;
		else if (y <= m) return l->rf(x, y);
		else if (x > m) return r->rf(x, y);
		else{
			int v = r->rf(m + 1, y);
			return (v != -1 ? v : l->rf(x, m));
		}
	}
};
node *lst, *rst;
node2 *proots[MAXN];
vector<int> disc; int dsz;
void init(int N, vector<int> H){
	node *root = new node(0, N - 1, H);
	vector<int> ld(N), rd(N), fd(N);
	vector<int> st; st.push_back(-1);
	for (int i = 0; i < N; i++){
		while (st.back() != -1 && H[st.back()] > H[i]) st.pop_back();
		ld[i] = max(0, root->query(st.back() + 1, i - 1) - H[i]);
		st.push_back(i);
	}
	st.clear(); st.push_back(N);
	for (int i = N - 1; i >= 0; i--){
		while (st.back() != N && H[st.back()] > H[i]) st.pop_back();
		rd[i] = max(0, root->query(i + 1, st.back() - 1) - H[i]);
		st.push_back(i);
	}
	lst = new node(0, N - 1, ld); rst = new node(0, N - 1, rd);
	for (int i = 0; i < N; i++){
		fd[i] = min(ld[i], rd[i]);
		disc.push_back(fd[i]);
	}
	sort(disc.begin(), disc.end());
	disc.resize(distance(disc.begin(), unique(disc.begin(), disc.end())));
	dsz = disc.size();
	vector<vector<int>> ord(dsz + 1);
	for (int i = 0; i < N; i++){
		int id = lower_bound(disc.begin(), disc.end(), fd[i]) - disc.begin();
		ord[dsz - id].push_back(i);
	}
	proots[0] = new node2(0, N - 1);
	for (int i = 1; i <= dsz; i++){
		proots[i] = new node2(proots[i - 1]);
		for (int x : ord[i]) proots[i]->update(x, 1);
	}
}
int max_towers(int L, int R, int D){
	int id = dsz - (lower_bound(disc.begin(), disc.end(), D) - disc.begin());
	int ans = proots[id]->cnt(L, R);
	if (ans == 0) return 1;
	int lb = proots[id]->lf(L, R), rb = proots[id]->rf(L, R);
	if (rst->query(L, lb - 1) >= D) ans++;
	if (lst->query(rb + 1, R) >= D) ans++;
	return ans;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 2136 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 3 ms 2136 KB Output is correct
5 Correct 3 ms 2136 KB Output is correct
6 Correct 3 ms 2136 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 3 ms 2136 KB Output is correct
9 Correct 3 ms 2136 KB Output is correct
10 Correct 3 ms 2136 KB Output is correct
11 Correct 2 ms 2136 KB Output is correct
12 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 2136 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 3 ms 2136 KB Output is correct
5 Correct 3 ms 2136 KB Output is correct
6 Correct 3 ms 2136 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 3 ms 2136 KB Output is correct
9 Correct 3 ms 2136 KB Output is correct
10 Correct 3 ms 2136 KB Output is correct
11 Correct 2 ms 2136 KB Output is correct
12 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 121520 KB Output is correct
2 Correct 1051 ms 122740 KB Output is correct
3 Correct 1020 ms 122484 KB Output is correct
4 Correct 1066 ms 124356 KB Output is correct
5 Correct 1038 ms 124332 KB Output is correct
6 Correct 1104 ms 124288 KB Output is correct
7 Correct 1020 ms 124240 KB Output is correct
8 Correct 774 ms 119336 KB Output is correct
9 Correct 783 ms 119476 KB Output is correct
10 Correct 1012 ms 119184 KB Output is correct
11 Correct 901 ms 119404 KB Output is correct
12 Incorrect 810 ms 119444 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 27156 KB Output is correct
2 Correct 830 ms 122428 KB Output is correct
3 Incorrect 813 ms 122736 KB 69174th lines differ - on the 1st token, expected: '2', found: '1'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 2136 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 3 ms 2136 KB Output is correct
5 Correct 3 ms 2136 KB Output is correct
6 Correct 3 ms 2136 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 3 ms 2136 KB Output is correct
9 Correct 3 ms 2136 KB Output is correct
10 Correct 3 ms 2136 KB Output is correct
11 Correct 2 ms 2136 KB Output is correct
12 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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