Submission #292890

#	Time	Username	Problem	Language	Result	Execution time	Memory
292890		arnold518	Two Antennas (JOI19_antennas)	C++14	100 / 100	1209 ms	39388 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e17;

struct Query
{
	int l, r, p;
};

int N, Q;
int A[MAXN+10], B[MAXN+10], H[MAXN+10];
Query C[MAXN+10];

struct Node
{
	ll lazy, val, val2;
	Node() : lazy(-INF), val(-INF), val2(-INF) {}
};

Node tree[MAXN*4+10];
ll P[MAXN+10], ans[MAXN+10];

Node operator + (Node p, Node q)
{
	Node ret;
	ret.val=max(p.val, q.val);
	ret.val2=max(p.val2, q.val2);
	return ret;
}

void busy(int node, int tl, int tr)
{
	tree[node].val=max(tree[node].val, tree[node].val2+tree[node].lazy);
	if(tl!=tr) tree[node*2].lazy=max(tree[node*2].lazy, tree[node].lazy), tree[node*2+1].lazy=max(tree[node*2+1].lazy, tree[node].lazy);
	else P[tl]=max(P[tl], tree[node].lazy);
	tree[node].lazy=-INF;
}

void init(int node, int tl, int tr)
{
	tree[node]=Node();
	if(tl==tr)
	{
		P[tl]=-INF;
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
}

void update1(int node, int tl, int tr, int l, int r, ll k)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		tree[node].lazy=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid, l, r, k);
	update1(node*2+1, mid+1, tr, l, r, k);
	tree[node]=tree[node*2]+tree[node*2+1];
}

void update2(int node, int tl, int tr, int p, ll k)
{
	busy(node, tl, tr);
	if(tr<p || p<tl) return;
	if(tl==tr)
	{
		tree[node].val2=k;
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, p, k);
	update2(node*2+1, mid+1, tr, p, k);
	tree[node]=tree[node*2]+tree[node*2+1];
}

ll query(int node, int tl, int tr, int l, int r)
{
	busy(node, tl, tr);
	if(l<=tl && tr<=r) return tree[node].val;
	if(r<tl || tr<l) return -INF;
	int mid=tl+tr>>1;
	return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1 ,tr, l, r));
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d%d", &H[i], &A[i], &B[i]);
	scanf("%d", &Q);
	for(int i=1; i<=Q; i++) scanf("%d%d", &C[i].l, &C[i].r), C[i].p=i;

	sort(C+1, C+Q+1, [&](const Query &p, const Query &q) { return p.r<q.r; });
	
	vector<pii> V;
	for(int i=1; i<=N; i++)
	{
		V.push_back({i+A[i], i});
		V.push_back({i+B[i]+1, -i});
	}	
	sort(V.begin(), V.end());

	for(int i=1; i<=Q; i++) ans[i]=-INF;

	init(1, 1, N);
	for(int i=1, j=0, k=1; i<=N; i++)
	{
		for(; j<V.size() && V[j].first<=i; j++)
		{
			if(V[j].second>0) 
			{
				update2(1, 1, N, V[j].second, -H[V[j].second]);
			}
			else
			{
				update2(1, 1, N, -V[j].second, -INF);
			}
		}
		int l=i-B[i], r=i-A[i];
		update1(1, 1, N, l, r, H[i]);
		for(; k<=Q && C[k].r==i; k++)
		{
			ans[C[k].p]=max(ans[C[k].p], query(1, 1, N, C[k].l, C[k].r));
		}
	}

	for(int i=1; i<=N; i++) H[i]=-H[i];
	init(1, 1, N);
	for(int i=1, j=0, k=1; i<=N; i++)
	{
		for(; j<V.size() && V[j].first<=i; j++)
		{
			if(V[j].second>0) 
			{
				update2(1, 1, N, V[j].second, -H[V[j].second]);
			}
			else
			{
				update2(1, 1, N, -V[j].second, -INF);
			}
		}
		int l=i-B[i], r=i-A[i];
		update1(1, 1, N, l, r, H[i]);
		for(; k<=Q && C[k].r==i; k++)
		{
			ans[C[k].p]=max(ans[C[k].p], query(1, 1, N, C[k].l, C[k].r));
		}
	}

	for(int i=1; i<=Q; i++)
	{
		if(ans[i]<0) ans[i]=-1;
		printf("%lld\n", ans[i]);
	}
}

Compilation message (stderr)

antennas.cpp: In function 'void init(int, int, int)':
antennas.cpp:53:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid=tl+tr>>1;
      |          ~~^~~
antennas.cpp: In function 'void update1(int, int, int, int, int, ll)':
antennas.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  int mid=tl+tr>>1;
      |          ~~^~~
antennas.cpp: In function 'void update2(int, int, int, int, ll)':
antennas.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |  int mid=tl+tr>>1;
      |          ~~^~~
antennas.cpp: In function 'll query(int, int, int, int, int)':
antennas.cpp:94:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |  int mid=tl+tr>>1;
      |          ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:120:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(; j<V.size() && V[j].first<=i; j++)
      |         ~^~~~~~~~~
antennas.cpp:143:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |   for(; j<V.size() && V[j].first<=i; j++)
      |         ~^~~~~~~~~
antennas.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
antennas.cpp:101:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  for(int i=1; i<=N; i++) scanf("%d%d%d", &H[i], &A[i], &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
antennas.cpp:103:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |  for(int i=1; i<=Q; i++) scanf("%d%d", &C[i].l, &C[i].r), C[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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