Submission #521731

#	Time	Username	Problem	Language	Result	Execution time	Memory
521731		blue	Two Antennas (JOI19_antennas)	C++17	100 / 100	842 ms	63564 KiB

antennas

#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 pushLazy(int i, ll V)
	{
		maxLP[i] = max(maxLP[i], V);
		rawAns[i] = max(rawAns[i], maxLP[i] - minH[i]);
	}
 
	void setH(ll I, ll V, ll i = 1, ll lzv = -INF)
	{
		// cerr << "setH" << ' ' << I << ' ' << V << ' ' << i << ' ' << l[i] << " - " << r[i] << ' ' << lzv << '\n';
		if(l[i] == r[i]) 
		{
			rawAns[i] = max(rawAns[i], max(lzv, maxLP[i]) - minH[i]);
			minH[i] = V;
			maxLP[i] = -INF;
		}
		else 
		{
			if(I <= (l[i]+r[i])/2) 
			{
				setH(I, V, 2*i, max(lzv, maxLP[i]));
				pushLazy(2*i+1, max(lzv, maxLP[i]));
			}
			else 
			{
				setH(I, V, 2*i+1, max(lzv, maxLP[i]));
				pushLazy(2*i, max(lzv, maxLP[i]));
			}
 
			minH[i] = min(minH[2*i], minH[2*i+1]);
			//rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]}); //BAD

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

			maxLP[i] = -INF;
		}

		// cerr << i << ' ' << l[i] << ' ' << r[i] << " : " << minH[i] << ' ' << rawAns[i] << ' ' << maxLP[i] << '\n';
	}
 
	ll query(ll L, ll R, ll i = 1, ll topMaxLP = -INF)
	{

		// cerr << "query : " << L << ' ' << R << ' ' << i << ' ' << l[i] << ' ' << r[i] << " -> " << rawAns[i] << '\n';
		if(r[i] < L || R < l[i]) return -INF;
		else if(L <= l[i] && r[i] <= R)
		{
			// cerr << "case Z\n";
			// if(L == 2 && R == 2) cerr << "ZZZ " << topMaxLP << ' ' << minH[i] << ' ' << rawAns[i] << '\n';
			return max(topMaxLP - minH[i], rawAns[i]);
		}
		else
		{
			// if(L == 2 && R == 2) cerr << "YYY " << topMaxLP << ' ' << minH[i] << ' ' << rawAns[i] << '\n';
			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';
			// cerr << H[r] << "\n";
			// cerr << A[r] << ' ' << B[r] << '\n';
			for(ll i: to_enable[r]) 
				{
					// cerr << "enable : " << i << '\n';
					S.setH(i, H[i]);
				}

			// cerr << "answer 2 = " << S.query(2, 2) << "###\n\n\n";
			// cerr << "\n\n";

			for(ll i: to_disable[r]) 
				{
					// cerr << "disable : " << i << '\n';
					S.setH(i, INF);
				}
			// cerr << "answer 2 = " << S.query(2, 2) << "!!!\n\n\n";
 
			ll le = r - B[r];
			ll re = r - A[r];

			// cerr << "interval = " << le << ' ' << re << '\n';
 
			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: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65