Submission #200032

#	Time	Username	Problem	Language	Result	Execution time	Memory
200032		arnold518	Two Antennas (JOI19_antennas)	C++14	100 / 100	921 ms	31452 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 = 1e15;

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

int N, Q;
int H[MAXN+10], A[MAXN+10], B[MAXN+10];
ll ans[MAXN+10];
Query query[MAXN+10];

ll tree[MAXN*4+10], val[MAXN*4+10], lazy[MAXN*4+10];

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

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

void update(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)
	{
		lazy[node]=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, k);
	update(node*2+1, mid+1, tr, l, r, k);
	tree[node]=max(tree[node*2], tree[node*2+1]);
}

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

void update2(int node, int tl, int tr, int pos, ll k)
{
	busy(node, tl, tr);
	if(tl==tr)
	{
		val[node]=k;
		return;
	}
	int mid=tl+tr>>1;
	if(pos<=mid) update2(node*2, tl, mid, pos, k);
	else update2(node*2+1, mid+1, tr, pos, k);
	val[node]=max(val[node*2], val[node*2+1]);
}

void debug(int node, int tl, int tr)
{
	busy(node, tl, tr);
	printf("DEBUG %d %d : %d %d %d\n", tl, tr, tree[node], val[node], lazy[node]);
	if(tl==tr) return;
	int mid=tl+tr>>1;
	debug(node*2, tl, mid);
	debug(node*2+1, mid+1, tr);
}

int main()
{
	int i, j, k;

	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d%d%d", &H[i], &A[i], &B[i]);
	scanf("%d", &Q);
	for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i, ans[i]=-INF;
	sort(query+1, query+Q+1, [&](const Query &p, const Query &q) { return p.r<q.r; });
		
	vector<pii> todo;
	for(i=1; i<=N; i++)
	{
		todo.push_back({i+A[i], i});
		todo.push_back({i+B[i]+1, -i});
	}
	sort(todo.begin(), todo.end());

	init(1, 1, N);
	for(i=1, j=1, k=0; i<=N; i++)
	{
		int l=i-B[i], r=i-A[i];
		for(; k<todo.size() && todo[k].first==i; k++)
		{
			int t=todo[k].second;
			if(t>0) update2(1, 1, N, t, -H[t]);//, printf("UPDATE2 %d %d\n", t, -H[t]);
			else update2(1, 1, N, -t, -INF);//, printf("UPDATE3 %d %d\n", -t, -INF);
		}
		if(r>=1) update(1, 1, N, max(1, l), r, H[i]);//printf("UPDATE %d %d %d\n", max(1, l), r, H[i]);
		//debug(1, 1, N);

		for(; j<=Q && query[j].r==i; j++)
		{
			ans[query[j].p]=max(ans[query[j].p], qquery(1, 1, N, query[j].l, query[j].r));
			//printf("QUERY %lld %lld %lld\n", query[j].l, query[j].r, qquery(1, 1, N, query[j].l, query[j].r));
		}
	}

	init(1, 1, N);
	for(i=1, j=1, k=0; i<=N; i++)
	{
		int l=i-B[i], r=i-A[i];
		for(; k<todo.size() && todo[k].first<=i; k++)
		{
			int t=todo[k].second;
			if(t>0) update2(1, 1, N, t, H[t]);
			else update2(1, 1, N, -t, -INF);
		}
		if(r>=1) update(1, 1, N, max(1, l), r, -H[i]);

		for(; j<=Q && query[j].r==i; j++)
		{
			ans[query[j].p]=max(ans[query[j].p], qquery(1, 1, N, query[j].l, query[j].r));
		}
	}
	for(i=1; i<=Q; i++)
	{
		if(ans[i]<=-1e14) ans[i]=-1;
		printf("%lld\n", ans[i]);
	}
}

Compilation message (stderr)

antennas.cpp: In function 'void init(int, int, int)':
antennas.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
antennas.cpp: In function 'void update(int, int, int, int, int, ll)':
antennas.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
antennas.cpp: In function 'll qquery(int, int, int, int, int)':
antennas.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
antennas.cpp: In function 'void update2(int, int, int, int, ll)':
antennas.cpp:75:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
antennas.cpp: In function 'void debug(int, int, int)':
antennas.cpp:84:78: warning: format '%d' expects argument of type 'int', but argument 4 has type 'll {aka long long int}' [-Wformat=]
  printf("DEBUG %d %d : %d %d %d\n", tl, tr, tree[node], val[node], lazy[node]);
                                             ~~~~~~~~~~                       ^
antennas.cpp:84:78: warning: format '%d' expects argument of type 'int', but argument 5 has type 'll {aka long long int}' [-Wformat=]
antennas.cpp:84:78: warning: format '%d' expects argument of type 'int', but argument 6 has type 'll {aka long long int}' [-Wformat=]
antennas.cpp:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:113:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; k<todo.size() && todo[k].first==i; k++)
         ~^~~~~~~~~~~~
antennas.cpp:133:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; k<todo.size() && todo[k].first<=i; k++)
         ~^~~~~~~~~~~~
antennas.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
antennas.cpp:96:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d%d%d", &H[i], &A[i], &B[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
antennas.cpp:98:75: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i, ans[i]=-INF;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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