oj.uz

Submission #521709

# Submission time Handle Problem Language Result Execution time Memory
521709 2022-02-02T19:10:24 Z blue Two Antennas (JOI19_antennas) C++17
0 / 100
 385 ms 48728 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;

using vi = vector<ll>;

const ll mx = 200'000;
const ll INF = 1'000'000'005;

ll N, Q;
vi H(1+mx), A(1+mx), B(1+mx);
vi L(1+mx), R(1+mx);

const ll Z = (1<<18);

struct segtree
{
	vi minH, maxLP, rawAns, l, r;

	void build(ll i, ll lv, ll rv)
	{
		l[i] = lv, r[i] = rv;
		if(lv == rv)
		{
			minH[i] = +INF;
		}
		else
		{
			build(2*i, lv, (lv+rv)/2);
			build(2*i+1, (lv+rv)/2+1, rv);
			minH[i] = min(minH[2*i], minH[2*i+1]);
		}
	}

	void init()
	{
		minH = vi(Z<<1, INF);
		maxLP = vi(Z<<1, -INF);
		rawAns = vi(Z<<1, -INF);
		l = vi(Z<<1);
		r = vi(Z<<1);

		build(1, 1, N);
	}

	void deploy(ll L, ll R, ll V, ll i = 1)
	{
		if(r[i] < L || R < l[i]) return;
		else if(L <= l[i] && r[i] <= R)
		{
			maxLP[i] = max(maxLP[i], V);
			rawAns[i] = max(rawAns[i], maxLP[i] - minH[i]);
		}
		else
		{
			deploy(L, R, V, 2*i);
			deploy(L, R, V, 2*i+1);

			rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]});
		}
	}

	void setH(ll I, ll V, ll i = 1)
	{
		if(l[i] == r[i]) minH[i] = V;
		else 
		{
			if(I <= (l[i]+r[i])/2) setH(I, V, 2*i);
			else setH(I, V, 2*i+1);

			minH[i] = min(minH[2*i], minH[2*i+1]);
			rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]});
		}
	}

	ll query(ll L, ll R, ll i = 1, ll topMaxLP = -INF)
	{
		if(r[i] < L || R < l[i]) return -INF;
		else if(L <= l[i] && r[i] <= R)
		{
			return max(topMaxLP - minH[i], rawAns[i]);
		}
		else
		{
			topMaxLP = max(topMaxLP, maxLP[i]);
			return max(query(L, R, 2*i, topMaxLP), query(L, R, 2*i+1, topMaxLP));
		}
	}
};


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for(ll i = 1; i <= N; i++)
	{
		cin >> H[i] >> A[i] >> B[i];
	}

	cin >> Q;

	for(ll j = 1; j <= Q; j++)
	{
		cin >> L[j] >> R[j];
	}


	vi res(1+Q, -1);

	segtree S;

	for(ll t = 0; t < 2; t++)
	{
		// cerr << "\n\n\n t = " << t << '\n';
		if(t == 1)
		{
			for(ll i = 1; 2*i <= N; i++)
			{
				swap(H[i], H[N-i+1]);
				swap(A[i], A[N-i+1]);
				swap(B[i], B[N-i+1]);
			}

			for(ll j = 1; j <= Q; j++)
			{
				L[j] = N+1 - L[j];
				R[j] = N+1 - R[j];
				swap(L[j], R[j]);

				// cerr << L[j] << " <> "  << R[j] << "\n";
			}
		}

		// cerr << "\n\n\n t = " << t << '\n';
		// for(ll i = 1; i <= N; i++) cerr << i << " : " << H[i] << ' ' << A[i] << ' ' << B[i] << '\n';


		vi R_occ[1+N];
		for(ll j = 1; j <= Q; j++)
		R_occ[R[j]].push_back(j);

		vi to_enable[1+N], to_disable[1+N];

		for(ll i = 1; i <= N; i++)
		{
			if(i + A[i] <= N) to_enable[i+A[i]].push_back(i);
			if(i + B[i] + 1 <= N) to_disable[i+B[i]+1].push_back(i);
		}

		S.init();

		for(ll r = 1; r <= N; r++)
		{
			// cerr << "\n\n r = " << r << '\n';
			for(ll i: to_enable[r]) 
				{
					// cerr << "enable : " << i << '\n';
					S.setH(i, H[i]);
				}
			for(ll i: to_disable[r]) 
				{
					// cerr << "disable : " << i << '\n';
					S.setH(i, INF);
				}

			ll le = r - B[r];
			ll re = r - A[r];

			if(1 <= re) 
			{
				// cerr << "deploy : " << le << ' ' << re << ' ' << H[r] << '\n';
				S.deploy(le, re, H[r]);
			}


			// for(ll i = 1; i <= N; i++) cerr << S.query(i, i) << ' ';
			// 	cerr << '\n';

			for(ll j: R_occ[r])
				res[j] = max(res[j], S.query(L[j], R[j]));
		}
	}

	for(ll j = 1; j <= Q; j++) cout << res[j] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 32828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 32828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 48728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 32828 KB Output isn't correct
2 Halted 0 ms 0 KB -