Submission #122809

#	Time	Username	Problem	Language	Result	Execution time	Memory
122809		WhipppedCream	Two Antennas (JOI19_antennas)	C++17	100 / 100	1040 ms	48744 KiB

antennas

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
 
const int maxn = 2e5+5;
 
int n, q;
 
ll H[maxn];
int A[maxn], B[maxn];
int ql[maxn], qr[maxn];
 
ll Res[maxn];
 
vector<int> buck[maxn];
vector<int> que[maxn];
 
ll tmp[maxn];
const int inf = 1234567890;
struct segtree
{
	struct node
	{
		ll a = -1, b = inf;
		ll res = -1;
	};
	node st[6*maxn];
	void clear()
	{
		for(int i = 0; i<= 4*n; i++)
		{
			st[i] = node();
			assert(st[i].a == -1);
		}
	}
	void build(ll *arr, int p = 1, int L = 1, int R = n)
	{
		if(L == R)
		{
			st[p].a = arr[L];
			return;
		}
		int M = (L+R)/2;
		build(arr, 2*p, L, M);
		build(arr, 2*p+1, M+1, R);
	}
	void modb(int p, ll x)
	{
		st[p].b = min(st[p].b, x);
		st[p].res = max(st[p].res, st[p].a-st[p].b);
	}
	void push(int p)
	{
        modb(2*p, st[p].b);
        modb(2*p+1, st[p].b);
        st[p].b = inf;
	}
	void update(int p)
	{
		assert(st[p].b == inf);
		st[p].a = max(st[2*p].a, st[2*p+1].a);
		st[p].res = max({st[p].res, st[2*p].res, st[2*p+1].res, st[p].a-st[p].b});
	}
	void rngb(int i, int j, ll dx, int p = 1, int L = 1, int R = n)
	{
		if(i> R || j< L) return;
		if(i<= L && R<= j)
		{
			modb(p, dx);
			return;
		}
		push(p);
		int M = (L+R)/2;
		rngb(i, j, dx, 2*p, L, M);
		rngb(i, j, dx, 2*p+1, M+1, R);
		update(p);
	}
	void pointa(int x, ll dx, int p = 1, int L = 1, int R = n)
	{
		if(L == R)
		{
			st[p].a += dx;
			st[p].b = inf;
			return;
		}
		push(p);
		int M = (L+R)/2;
		if(x<= M) pointa(x, dx, 2*p, L, M);
		else pointa(x, dx, 2*p+1, M+1, R);
		update(p);
	}
	ll ask(int i, int j, int p = 1, int L = 1, int R = n)
	{
		if(i> R || j< L) return -1;
		if(i<= L && R<= j) return st[p].res;
		push(p);
		int M = (L+R)/2;
		ll x = ask(i, j, 2*p, L, M);
		ll y = ask(i, j, 2*p+1, M+1, R);
		return max(x, y);
	}
};
 
segtree foo;
 
void solve()
{
	foo.clear();
	for(int i = 0; i<= n; i++) buck[i].clear();
	for(int i = 0; i<= n; i++) que[i].clear();
	for(int i = 1; i<= n; i++)
	{
		buck[max(1, i-A[i]+1)].pb(i);
		buck[max(1, i-B[i])].pb(-i);
	}
	for(int i = 1; i<= q; i++)
	{
		que[ql[i]].pb(i);
	}
	for(int i = 1; i<= n; i++) tmp[i] = H[i]-1e9;
	foo.build(tmp);
	for(int i = n; i>= 1; i--)
	{
		foo.rngb(min(i+A[i], n+1), min(i+B[i], n), H[i]);
		for(int k : que[i])
		{
			Res[k] = max(Res[k], foo.ask(ql[k], qr[k]));
		}
		for(int x : buck[i])
		{
			if(x> 0) foo.pointa(x, 1e9);
			else foo.pointa(-x, -1e9);
		}
	}
}
 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++)
	{
		scanf("%lld %d %d", &H[i], &A[i], &B[i]);
	}
	scanf("%d", &q);
	for(int i = 1; i<= q; i++)
	{
		scanf("%d %d", &ql[i], &qr[i]);
	}
	memset(Res, -1, sizeof Res);
	solve();
	reverse(H+1, H+n+1);
	reverse(A+1, A+n+1);
	reverse(B+1, B+n+1);
    for(int i = 1; i<= q; i++)
    {
    	int l = ql[i], r = qr[i];
    	ql[i] = n+1-r;
    	qr[i] = n+1-l;
    	assert(ql[i]<= qr[i]);
    }
    solve();
    for(int i = 1; i<= q; i++) printf("%lld\n", Res[i]);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %d %d", &H[i], &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &ql[i], &qr[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65