oj.uz

Submission #987809

# Submission time Handle Problem Language Result Execution time Memory
987809 2024-05-23T15:49:13 Z siewjh Radio Towers (IOI22_towers) C++17
0 / 100
 1122 ms 122568 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);
	int lb = (ans == 0 ? R + 1 : proots[id]->lf(L, R)), rb = (ans == 0 ? L - 1 : 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 515 ms 69148 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
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 4 ms 2136 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 4 ms 2136 KB Output is correct
9 Correct 3 ms 2340 KB Output is correct
10 Incorrect 2 ms 2136 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 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 4 ms 2136 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 4 ms 2136 KB Output is correct
9 Correct 3 ms 2340 KB Output is correct
10 Incorrect 2 ms 2136 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 121740 KB Output is correct
2 Correct 1122 ms 122540 KB Output is correct
3 Incorrect 1070 ms 122508 KB 18409th lines differ - on the 1st token, expected: '1', found: '0'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 27224 KB Output is correct
2 Incorrect 892 ms 122568 KB 13344th lines differ - on the 1st token, expected: '1', found: '0'
3 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 4 ms 2136 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 4 ms 2136 KB Output is correct
9 Correct 3 ms 2340 KB Output is correct
10 Incorrect 2 ms 2136 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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