Submission #1313459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313459		neonglitch	Simple (info1cup19_simple)	C++20	100 / 100	365 ms	27264 KiB

subway

#include <iostream>
using namespace std;
#define int long long
const int inf=1e18;
const int N=1e6+100;
int a[N],seg[N][4],n,lazy[N];
void build(int v=1,int l=1,int r=n)
{
	if(l==r)
	{
		seg[v][0]=seg[v][1]=-inf; // max
		seg[v][2]=seg[v][3]=inf; // min
		seg[v][a[l]%2]=a[l];
		seg[v][2+(a[l]%2)]=a[l];
		return;
	}
	int m=(l+r)>>1,lc=v<<1,rc=lc|1;
	build(lc,l,m);
	build(rc,m+1,r);
	seg[v][0]=max(seg[lc][0],seg[rc][0]);
	seg[v][1]=max(seg[lc][1],seg[rc][1]);
	seg[v][2]=min(seg[lc][2],seg[rc][2]);
	seg[v][3]=min(seg[lc][3],seg[rc][3]);
}
void push(int v,int l,int r)
{
	int m=(l+r)>>1,lc=v<<1,rc=lc|1;
	if(lazy[v]&1)
	{
		swap(seg[v][0],seg[v][1]);
		swap(seg[v][2],seg[v][3]);
	}
	seg[v][0]+=lazy[v];
	seg[v][1]+=lazy[v];
	seg[v][2]+=lazy[v];
	seg[v][3]+=lazy[v];
	if(l!=r)
	{
		lazy[lc]+=lazy[v];
		lazy[rc]+=lazy[v];
	}
	lazy[v]=0;
}
void update(int ql,int qr,int qv,int l=1,int r=n,int v=1)
{
	push(v,l,r);
	if(qr<l or r<ql)
	{
		return;
	}
	if(ql<=l and r<=qr)
	{
		lazy[v]+=qv;
		push(v,l,r);
		return;
	}
	int m=(l+r)>>1,lc=v<<1,rc=lc|1;
	update(ql,qr,qv,l,m,lc);
	update(ql,qr,qv,m+1,r,rc);
	seg[v][0]=max(seg[lc][0],seg[rc][0]);
	seg[v][1]=max(seg[lc][1],seg[rc][1]);
	seg[v][2]=min(seg[lc][2],seg[rc][2]);
	seg[v][3]=min(seg[lc][3],seg[rc][3]);
}
pair<int,int> get(int ql,int qr,int l=1,int r=n,int v=1)
{
	push(v,l,r);
	if(qr<l or r<ql)
	{
		return {inf,-inf};
	}
	if(ql<=l and r<=qr)
	{
		return {seg[v][2],seg[v][1]};
	}
	int m=(l+r)>>1,lc=v<<1,rc=lc|1;
	auto a1=get(ql,qr,l,m,lc);
	auto a2=get(ql,qr,m+1,r,rc);
	return {min(a1.first,a2.first),max(a1.second,a2.second)};
}
main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build();
	int q;
	cin>>q;
	while(q--)
	{
		int ty;
		cin>>ty;
		if(!ty)
		{
			int l,r,v;
			cin>>l>>r>>v;
			update(l,r,v);
			// cout<<"NEW ";
			// for(int i=1;i<=n;i++)
			// {
				// cout<<max(get(i,i).first,get(i,i).second)<<' ';
			// }
			// cout<<endl;
		}
		else{
			int l,r;
			cin>>l>>r;
			auto ans=get(l,r);
			if(ans.first>=inf)
			{
				ans.first=-1;
			}
			if(ans.second<0)
			{
				ans.second=-1;
			}
			// even odd
			cout<<ans.first<<' '<<ans.second<<endl;
		}
	}
}

Compilation message (stderr)

subway.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main()
      | ^~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40