Submission #344285

#	Time	Username	Problem	Language	Result	Execution time	Memory
344285		TadijaSebez	Triple Jump (JOI19_jumps)	C++11	100 / 100	1520 ms	67308 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=500050;
const int M=2*N;
const int inf=1e9+7;
int a[N],ls[M],rs[M],tsz,root,mx1[M],mx2[M],lzy[M];
void Build(int &c, int ss, int se)
{
	c=++tsz;mx2[c]=-inf;lzy[c]=-inf;
	if(ss==se){ mx1[c]=a[ss];return;}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
	mx1[c]=max(mx1[ls[c]],mx1[rs[c]]);
}
void Upd(int c, int 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 Set(int c, int ss, int se, int qs, int qe, int 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;
	Set(ls[c],ss,mid,qs,qe,x);
	Set(rs[c],mid+1,se,qs,qe,x);
	mx2[c]=max(mx2[ls[c]],mx2[rs[c]]);
}
int 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,ans[N];
vector<pair<int,int>> Qs[N];
void Add(int x, int y)
{
	int z=y+y-x;
	//printf("%i %i %i\n",x,y,z);
    Set(root,1,n,z,n,a[x]+a[y]);
}
void Solve()
{
	stack<int> st;
	for(int i=n;i>=1;i--)
	{
        while(st.size() && a[st.top()]<=a[i])
		{
			Add(i,st.top());
			st.pop();
		}
		if(st.size()) Add(i,st.top());
		st.push(i);
		for(auto qu:Qs[i])
		{
			ans[qu.second]=Get(root,1,n,i,qu.first);
			//printf("%i:(%i %i)\n",qu.second,i,qu.first);
		}
	}
	//for(int i=1;i<=n;i++) printf("%i ",Get(root,1,n,i,i));printf("\n");
}
int main()
{
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]);
	Build(root,1,n);
	scanf("%i",&q);
	for(int i=1;i<=q;i++)
	{
		int l,r;
		scanf("%i %i",&l,&r);
		Qs[l].pb({r,i});
	}
	Solve();
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void Build(int&, int, int)':
jumps.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int mid=ss+se>>1;
      |          ~~^~~
jumps.cpp: In function 'void Set(int, int, int, int, int, int)':
jumps.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int mid=ss+se>>1;
      |          ~~^~~
jumps.cpp: In function 'int Get(int, int, int, int, int)':
jumps.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid=ss+se>>1;
      |          ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
jumps.cpp:80:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  for(int i=1;i<=n;i++) scanf("%i",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~
jumps.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
jumps.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   scanf("%i %i",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54