제출 #126884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126884		TadijaSebez	Two Antennas (JOI19_antennas)	C++11	100 / 100	1169 ms	49760 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=200050;
const int M=2*N;
const ll inf=1e18;
int h[N],a[N],b[N];
ll ans[N];
vector<pair<int,int>> Qs[N];
vector<int> add[N],del[N];
int root,tsz,ls[M],rs[M];
ll mx1[M],mx2[M],lzy[M];
void Build(int &c, int ss, int se)
{
	c=++tsz;mx1[c]=mx2[c]=lzy[c]=-inf;
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void upd(int c, ll x)
{
	mx2[c]=max(mx2[c],mx1[c]+x);
	lzy[c]=max(lzy[c],x);
}
void push(int c)
{
	if(lzy[c]!=-inf)
	{
		upd(ls[c],lzy[c]);
		upd(rs[c],lzy[c]);
		lzy[c]=-inf;
	}
}
void Add(int c, int ss, int se, int qs, int qe, ll x)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ upd(c,x);return;}
	push(c);
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,x);
	Add(rs[c],mid+1,se,qs,qe,x);
	mx2[c]=max(mx2[ls[c]],mx2[rs[c]]);
}
void Set(int c, int ss, int se, int qi, ll x)
{
	if(ss==se){ mx1[c]=x;return;}
	push(c);
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,x);
	else Set(rs[c],mid+1,se,qi,x);
	mx1[c]=max(mx1[ls[c]],mx1[rs[c]]);
}
ll Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return -inf;
	if(qs<=ss && qe>=se) return mx2[c];
	push(c);
	int mid=ss+se>>1;
	return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
int n,q;
void Solve()
{
	Build(root,1,n);
	for(int i=1;i<=n;i++)
	{
		int l=i+a[i],r=i+b[i];
		l=min(l,n+1);
		r=min(r,n+1);
		add[l].pb(i);
		del[r].pb(i);
		for(int x:add[i]) Set(root,1,n,x,h[x]);
		Add(root,1,n,i-b[i],i-a[i],-h[i]);
		for(auto t:Qs[i]) ans[t.second]=max(ans[t.second],Get(root,1,n,t.first,i));
		for(int x:del[i]) Set(root,1,n,x,-inf);
		add[i].clear();
		del[i].clear();
	}
	for(int i=1;i<=tsz;i++) ls[i]=rs[i]=0;
	tsz=root=0;
}
int main()
{
	int l,r;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i %i %i",&h[i],&a[i],&b[i]);
	scanf("%i",&q);
	for(int i=1;i<=q;i++) scanf("%i %i",&l,&r),Qs[r].pb({l,i}),ans[i]=-1;
	Solve();
	for(int i=1;i<=n;i++) h[i]=-h[i];
	Solve();
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'void Build(int&, int, int)':
antennas.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'void Add(int, int, int, int, int, long long int)':
antennas.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'void Set(int, int, int, int, long long int)':
antennas.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'long long int Get(int, int, int, int, int)':
antennas.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
antennas.cpp:88:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i %i",&h[i],&a[i],&b[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
antennas.cpp:90:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i %i",&l,&r),Qs[r].pb({l,i}),ans[i]=-1;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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