oj.uz

Submission #833234

# Submission time Handle Problem Language Result Execution time Memory
833234 2023-08-22T03:28:50 Z pavement Radio Towers (IOI22_towers) C++17
0 / 100
 835 ms 38564 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;
bool is_init;
vector<int> H, cl, cr;
vector<vector<int> > anc;
vector<ii> segs;

void init(int N, vector<int> H) {
	::N = N;
	::H = H;
	cl = vector<int>(N, -1);
	cr = vector<int>(N, N);
	anc = vector<vector<int> >(20, vector<int>(N, -1));
}

struct node {
	node *left, *right;
	int S, E;
	ii val;
	node(int _s, int _e) : S(_s), E(_e), val(-1, -1) {
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void upd(int p, ii v) {
		val = max(val, v);
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->upd(p, v);
		} else {
			right->upd(p, v);
		}
	}
	ii qry(int r) {
		if (r < S) {
			return mp(-1, -1);
		}
		if (E <= r) {
			return val;
		}
		return max(left->qry(r), right->qry(r));
	}
} *root;

int max_towers(int L, int R, int D) {
	if (!is_init) {
		vector<ii> vec;
		for (int i = 0; i < N; i++) {
			{
				int lo = 0, hi = (int)vec.size() - 1;
				while (lo <= hi) {
					int mid = (lo + hi) / 2;
					if (vec[mid].first <= H[i] - D) {
						cl[i] = vec[mid].second;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}
			}
			while (!vec.empty() && vec.back().first >= H[i]) {
				vec.pop_back();
			}
			vec.eb(H[i], i);
		}
		vec.clear();
		for (int i = N - 1; i >= 0; i--) {
			{
				int lo = 0, hi = (int)vec.size() - 1;
				while (lo <= hi) {
					int mid = (lo + hi) / 2;
					if (vec[mid].first <= H[i] - D) {
						cr[i] = vec[mid].second;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}
			}
			while (!vec.empty() && vec.back().first >= H[i]) {
				vec.pop_back();
			}
			vec.eb(H[i], i);
		}
		for (int i = 0; i < N; i++) {
			if (cl[i] != -1 && cr[i] != N) {
				segs.eb(cr[i], cl[i]);
			}
		}
		sort(segs.begin(), segs.end());
		root = new node(0, N - 1);
		for (int i = 0; i < (int)segs.size(); i++) {
			int to = root->qry(segs[i].second).second;
			anc[0][i] = to;
			for (int k = 1; k < 20; k++) {
				if (anc[k - 1][i] == -1) {
					break;
				}
				anc[k][i] = anc[k - 1][anc[k - 1][i]];
			}
			root->upd(segs[i].first, mp(segs[i].second, i));
		}
		is_init = 1;
	}
	int st = root->qry(R).second;
	if (segs[st].second < L) {
		return 1;
	}
	int ans = 2;
	for (int k = 19; k >= 0; k--) {
		if (anc[k][st] != -1 && segs[anc[k][st]].second >= L) {
			st = anc[k][st];
			ans += (1 << k);
		}
	}
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 12212 KB 31st 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 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Runtime error 1 ms 1104 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Runtime error 1 ms 1104 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 19740 KB Output is correct
2 Correct 835 ms 19868 KB Output is correct
3 Correct 800 ms 19828 KB Output is correct
4 Correct 761 ms 19872 KB Output is correct
5 Correct 719 ms 19888 KB Output is correct
6 Correct 808 ms 19892 KB Output is correct
7 Correct 700 ms 19872 KB Output is correct
8 Runtime error 38 ms 38564 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Runtime error 1 ms 1104 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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