oj.uz

Submission #832426

# Submission time Handle Problem Language Result Execution time Memory
832426 2023-08-21T10:15:06 Z ymm Radio Towers (IOI22_towers) C++17
4 / 100
 858 ms 49352 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 = 100'010;

template<class T, class CMP>
struct rmq {
	static int constexpr lg = 18;
	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;
	auto [x, y] = rmq_mx.get(L, R);
	if (x - max(height[L], height[R-1]) < D)
		return 1;
	return 2;
#if 0
	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;
#endif
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 32528 KB Output is correct
2 Correct 817 ms 49352 KB Output is correct
3 Correct 725 ms 49236 KB Output is correct
4 Correct 743 ms 49336 KB Output is correct
5 Correct 858 ms 49348 KB Output is correct
6 Correct 720 ms 49292 KB Output is correct
7 Correct 776 ms 49300 KB Output is correct
8 Correct 4 ms 9680 KB Output is correct
9 Correct 5 ms 10200 KB Output is correct
10 Correct 5 ms 10192 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9808 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 4 ms 9808 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 553 ms 48932 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 176 ms 18268 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 4 ms 9808 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 318 ms 32528 KB Output is correct
2 Correct 817 ms 49352 KB Output is correct
3 Correct 725 ms 49236 KB Output is correct
4 Correct 743 ms 49336 KB Output is correct
5 Correct 858 ms 49348 KB Output is correct
6 Correct 720 ms 49292 KB Output is correct
7 Correct 776 ms 49300 KB Output is correct
8 Correct 4 ms 9680 KB Output is correct
9 Correct 5 ms 10200 KB Output is correct
10 Correct 5 ms 10192 KB Output is correct
11 Incorrect 4 ms 9808 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
12 Halted 0 ms 0 KB -