oj.uz

Submission #832412

# Submission time Handle Problem Language Result Execution time Memory
832412 2023-08-21T10:09:42 Z ymm Radio Towers (IOI22_towers) C++17
28 / 100
 924 ms 77568 KB 
#include "towers.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
using namespace std;

const int inf = 1e9+10;
const int N = 400'010;

template<class T, class CMP>
struct rmq {
	static int constexpr lg = 20;
	CMP cmp;
	typedef pair<T,int> el;
	vector<el> vec[lg];
	int sz;

	el mn(const el &x, const el &y) { return cmp(x.first, y.first)? x: y; }

	void init(const vector<T> &a) {
		sz = a.size();
		vec[0].resize(sz);
		Loop (i,0,sz)
			vec[0][i] = {a[i], i};
		Loop (j,0,lg-1) {
			if ((2<<j) > sz)
				break;
			vec[j+1].resize(sz-(2<<j)+1);
			for (int i = 0; i + (2<<j) <= sz; ++i)
				vec[j+1][i] = mn(vec[j][i], vec[j][i+(1<<j)]);
		}
	}
	el get(int l, int r) {
		int k = __lg(r-l);
		return mn(vec[k][l], vec[k][r-(1<<k)]);
	}
};
rmq<int, less<int>> rmq_mn;
rmq<int, greater<int>> rmq_mx;

namespace seg {
	vector<int> t[4*N];
	int sz;

	void init(const vector<int> &vec, int i, int b, int e) {
		if (e-b == 1) {
			t[i] = {vec[b]};
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		t[i].resize(t[2*i+1].size() + t[2*i+2].size());
		merge(t[2*i+1].begin(), t[2*i+1].end(),
		      t[2*i+2].begin(), t[2*i+2].end(),
		      t[i].begin());
	}
	void init(const vector<int> &vec) { sz = vec.size(); init(vec, 0, 0, sz); }

	int get(int l, int r, int d, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i].end() - lower_bound(t[i].begin(), t[i].end(), d);
		if (r <= b || e <= l)
			return 0;
		return   get(l, r, d, 2*i+1, b, (b+e)/2)
		       + get(l, r, d, 2*i+2, (b+e)/2, e);
	}
	int get(int l, int r, int d) { return get(l, r, d, 0, 0, sz); }

	int lrmost(int l, int r, int d, bool dir, int i, int b, int e) {
		if (r <= b || e <= l || t[i].back() < d)
			return -1;
		if (e-b == 1)
			return b;
		int ans = -1;
		ans = lrmost(l, r, d, dir, 2*i+1+ dir, dir? (b+e)/2: b, dir? e: (b+e)/2);
		if (ans != -1)
			return ans;
		ans = lrmost(l, r, d, dir, 2*i+1+!dir, dir? b: (b+e)/2, dir? (b+e)/2: e);
		return ans;
	}
	int leftmost(int l, int r, int d) { return lrmost(l, r, d, 0, 0, 0, sz); }
	int rightmost(int l, int r, int d) { return lrmost(l, r, d, 1, 0, 0, sz); }
}

int height[N];
int lsml[N], rsml[N];
int lval[N], rval[N], val[N];
int n;

void init_sml()
{
	vector<int> vec;
	Loop (i,0,n) {
		while (vec.size() && height[vec.back()] > height[i])
			vec.pop_back();
		lsml[i] = vec.size()? vec.back(): -1;
		vec.push_back(i);
	}
	vec.clear();
	LoopR (i,0,n) {
		while (vec.size() && height[vec.back()] > height[i])
			vec.pop_back();
		rsml[i] = vec.size()? vec.back(): n;
		vec.push_back(i);
	}
}

void init_val()
{
	Loop (i,0,n) {
		lval[i] = lsml[i] == -1? inf: lsml[i] == i-1? 0: rmq_mx.get(lsml[i]+1, i+1).first - height[i];
		rval[i] = rsml[i] ==  n? inf: rsml[i] == i+1? 0: rmq_mx.get(i, rsml[i]).first - height[i];
		val[i] = min(lval[i], rval[i]);
	}
	seg::init(vector<int>(val, val+n));
}

bool darre(int l, int r, int d, int i)
{
	int val = min(lsml[i] < l? inf: lval[i], rsml[i] >= r? inf: rval[i]);
	return val >= d;
}

void init(int N, std::vector<int> H)
{
	n = N;
	Loop (i,0,n)
		height[i] = H[i];
	rmq_mx.init(H);
	rmq_mn.init(H);
	init_sml();
	init_val();
}

int max_towers(int L, int R, int D)
{
	++R;
	int ans = seg::get(L, R, D);
	if (ans == 0) {
		ans = 1;
		int p = rmq_mx.get(L, R).second;
		if (p != L && p != R-1) {
			int pl = rmq_mn.get(L, p).second;
			int pr = rmq_mn.get(p+1, R).second;
			if (darre(L, R, D, pl) && darre(L, R, D, pr))
				ans = 2;
		}
		return ans;
	}
	int pl = seg::leftmost(L, R, D);
	int pr = seg::rightmost(L, R, D);
	if (pl != L) {
		int pll = rmq_mn.get(L, pl).second;
		ans += darre(L, R, D, pll);
	}
	if (pr != R-1) {
		int prr = rmq_mn.get(pr+1, R).second;
		ans += darre(L, R, D, prr);
	}
	return ans;
}

Subtask #1
0 / 4.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37956 KB Output is correct
2 Correct 16 ms 38368 KB Output is correct
3 Correct 23 ms 38368 KB Output is correct
4 Correct 20 ms 38436 KB Output is correct
5 Correct 19 ms 38360 KB Output is correct
6 Correct 22 ms 38440 KB Output is correct
7 Correct 19 ms 38364 KB Output is correct
8 Correct 19 ms 38480 KB Output is correct
9 Correct 22 ms 38480 KB Output is correct
10 Correct 20 ms 38480 KB Output is correct
11 Correct 23 ms 38376 KB Output is correct
12 Correct 18 ms 37836 KB Output is correct
13 Correct 20 ms 38448 KB Output is correct
14 Correct 25 ms 38464 KB Output is correct
15 Correct 18 ms 38480 KB Output is correct
16 Correct 22 ms 38480 KB Output is correct
17 Correct 17 ms 38480 KB Output is correct
18 Correct 21 ms 38476 KB Output is correct
19 Correct 19 ms 38352 KB Output is correct
20 Correct 20 ms 38432 KB Output is correct
21 Correct 24 ms 38480 KB Output is correct
22 Correct 20 ms 38480 KB Output is correct
23 Correct 20 ms 38408 KB Output is correct
24 Correct 21 ms 38436 KB Output is correct
25 Correct 20 ms 38052 KB Output is correct
26 Correct 19 ms 38448 KB Output is correct
27 Correct 20 ms 38420 KB Output is correct
28 Correct 20 ms 38352 KB Output is correct
29 Correct 20 ms 38468 KB Output is correct
30 Correct 20 ms 38436 KB Output is correct
31 Correct 20 ms 38368 KB Output is correct
32 Correct 20 ms 38360 KB Output is correct
33 Correct 20 ms 38432 KB Output is correct
34 Correct 19 ms 38448 KB Output is correct
35 Correct 20 ms 38448 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37956 KB Output is correct
2 Correct 16 ms 38368 KB Output is correct
3 Correct 23 ms 38368 KB Output is correct
4 Correct 20 ms 38436 KB Output is correct
5 Correct 19 ms 38360 KB Output is correct
6 Correct 22 ms 38440 KB Output is correct
7 Correct 19 ms 38364 KB Output is correct
8 Correct 19 ms 38480 KB Output is correct
9 Correct 22 ms 38480 KB Output is correct
10 Correct 20 ms 38480 KB Output is correct
11 Correct 23 ms 38376 KB Output is correct
12 Correct 18 ms 37836 KB Output is correct
13 Correct 20 ms 38448 KB Output is correct
14 Correct 25 ms 38464 KB Output is correct
15 Correct 18 ms 38480 KB Output is correct
16 Correct 22 ms 38480 KB Output is correct
17 Correct 17 ms 38480 KB Output is correct
18 Correct 21 ms 38476 KB Output is correct
19 Correct 19 ms 38352 KB Output is correct
20 Correct 20 ms 38432 KB Output is correct
21 Correct 24 ms 38480 KB Output is correct
22 Correct 20 ms 38480 KB Output is correct
23 Correct 20 ms 38408 KB Output is correct
24 Correct 21 ms 38436 KB Output is correct
25 Correct 20 ms 38052 KB Output is correct
26 Correct 19 ms 38448 KB Output is correct
27 Correct 20 ms 38420 KB Output is correct
28 Correct 20 ms 38352 KB Output is correct
29 Correct 20 ms 38468 KB Output is correct
30 Correct 20 ms 38436 KB Output is correct
31 Correct 20 ms 38368 KB Output is correct
32 Correct 20 ms 38360 KB Output is correct
33 Correct 20 ms 38432 KB Output is correct
34 Correct 19 ms 38448 KB Output is correct
35 Correct 20 ms 38448 KB Output is correct
36 Correct 48 ms 62928 KB Output is correct
37 Incorrect 81 ms 77476 KB 1st lines differ - on the 1st token, expected: '2946', found: '2945'
38 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 797 ms 77172 KB 29th lines differ - on the 1st token, expected: '9839', found: '9838'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 46436 KB Output is correct
2 Correct 847 ms 77520 KB Output is correct
3 Correct 924 ms 77524 KB Output is correct
4 Correct 782 ms 77512 KB Output is correct
5 Correct 676 ms 77516 KB Output is correct
6 Correct 910 ms 77524 KB Output is correct
7 Correct 829 ms 77528 KB Output is correct
8 Correct 520 ms 77456 KB Output is correct
9 Correct 720 ms 77524 KB Output is correct
10 Correct 710 ms 77492 KB Output is correct
11 Correct 644 ms 77480 KB Output is correct
12 Correct 73 ms 77492 KB Output is correct
13 Correct 65 ms 77468 KB Output is correct
14 Correct 74 ms 77556 KB Output is correct
15 Correct 58 ms 77488 KB Output is correct
16 Correct 60 ms 77568 KB Output is correct
17 Correct 65 ms 76056 KB Output is correct
18 Correct 65 ms 77508 KB Output is correct
19 Correct 65 ms 77484 KB Output is correct
20 Correct 69 ms 77452 KB Output is correct
21 Correct 74 ms 77460 KB Output is correct
22 Correct 78 ms 77512 KB Output is correct
23 Correct 72 ms 77544 KB Output is correct
24 Correct 58 ms 77516 KB Output is correct
25 Correct 66 ms 77552 KB Output is correct
26 Correct 67 ms 77568 KB Output is correct
27 Correct 58 ms 77448 KB Output is correct
28 Correct 20 ms 38424 KB Output is correct
29 Correct 19 ms 38376 KB Output is correct
30 Correct 20 ms 38416 KB Output is correct
31 Correct 19 ms 38352 KB Output is correct
32 Correct 20 ms 38440 KB Output is correct
33 Correct 23 ms 38032 KB Output is correct
34 Correct 20 ms 38460 KB Output is correct
35 Correct 20 ms 38484 KB Output is correct
36 Correct 20 ms 38504 KB Output is correct
37 Correct 24 ms 38396 KB Output is correct
38 Correct 20 ms 38344 KB Output is correct
39 Correct 20 ms 38480 KB Output is correct
40 Correct 21 ms 38444 KB Output is correct
41 Correct 19 ms 38412 KB Output is correct
42 Correct 19 ms 38416 KB Output is correct
43 Correct 20 ms 38352 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37956 KB Output is correct
2 Correct 16 ms 38368 KB Output is correct
3 Correct 23 ms 38368 KB Output is correct
4 Correct 20 ms 38436 KB Output is correct
5 Correct 19 ms 38360 KB Output is correct
6 Correct 22 ms 38440 KB Output is correct
7 Correct 19 ms 38364 KB Output is correct
8 Correct 19 ms 38480 KB Output is correct
9 Correct 22 ms 38480 KB Output is correct
10 Correct 20 ms 38480 KB Output is correct
11 Correct 23 ms 38376 KB Output is correct
12 Correct 18 ms 37836 KB Output is correct
13 Correct 20 ms 38448 KB Output is correct
14 Correct 25 ms 38464 KB Output is correct
15 Correct 18 ms 38480 KB Output is correct
16 Correct 22 ms 38480 KB Output is correct
17 Correct 17 ms 38480 KB Output is correct
18 Correct 21 ms 38476 KB Output is correct
19 Correct 19 ms 38352 KB Output is correct
20 Correct 20 ms 38432 KB Output is correct
21 Correct 24 ms 38480 KB Output is correct
22 Correct 20 ms 38480 KB Output is correct
23 Correct 20 ms 38408 KB Output is correct
24 Correct 21 ms 38436 KB Output is correct
25 Correct 20 ms 38052 KB Output is correct
26 Correct 19 ms 38448 KB Output is correct
27 Correct 20 ms 38420 KB Output is correct
28 Correct 20 ms 38352 KB Output is correct
29 Correct 20 ms 38468 KB Output is correct
30 Correct 20 ms 38436 KB Output is correct
31 Correct 20 ms 38368 KB Output is correct
32 Correct 20 ms 38360 KB Output is correct
33 Correct 20 ms 38432 KB Output is correct
34 Correct 19 ms 38448 KB Output is correct
35 Correct 20 ms 38448 KB Output is correct
36 Correct 48 ms 62928 KB Output is correct
37 Incorrect 81 ms 77476 KB 1st lines differ - on the 1st token, expected: '2946', found: '2945'
38 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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