Submission #365566

#	Time	Username	Problem	Language	Result	Execution time	Memory
365566		SlavicG	Simple (info1cup19_simple)	C++14	100 / 100	577 ms	32748 KiB

subway

#include "bits/stdc++.h"
 
using namespace std;
 
#define              ll              long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
#define         fastio               ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define int long long

struct T{
	int min_par, min_impar, max_impar, max_par;
};
T merge(T x, T y){
	int MN_PAR = -1, MXPAR = -1, MNIMPAR =-1,MXIMPAR=-1;
	if(x.min_par != -1)MN_PAR = x.min_par;
	if(y.min_par != -1)MN_PAR = y.min_par;
	if(x.min_par != -1)MN_PAR = min(MN_PAR, x.min_par);
	if(y.min_par != -1)MN_PAR = min(MN_PAR, y.min_par);

	if(x.max_par != -1)MXPAR = x.max_par;
	if(y.max_par != -1)MXPAR = y.max_par;
	if(x.max_par != -1)MXPAR = max(MXPAR, x.max_par);
	if(y.max_par != -1)MXPAR = max(MXPAR, y.max_par);


	if(x.max_impar != -1)MXIMPAR = x.max_impar;
	if(y.max_impar != -1)MXIMPAR = y.max_impar;
	if(x.max_impar != -1)MXIMPAR = max(MXIMPAR, x.max_impar);
	if(y.max_impar != -1)MXIMPAR = max(MXIMPAR, y.max_impar);

	if(x.min_impar != -1)MNIMPAR = x.min_impar;
	if(y.min_impar != -1)MNIMPAR = y.min_impar;
	if(x.min_impar != -1)MNIMPAR = min(MNIMPAR, x.min_impar);
	if(y.min_impar != -1)MNIMPAR = min(MNIMPAR, y.min_impar);

	return {MN_PAR,MNIMPAR,MXIMPAR,MXPAR};
}
const int maxn = 1e6;
T tree[maxn];
int lazy[maxn];

void push(int i, int l, int r)
{
	if(lazy[i] == 0)return;

	if(tree[i].min_par !=-1)tree[i].min_par += lazy[i];
	if(tree[i].min_impar != -1)tree[i].min_impar+=lazy[i];
	if(tree[i].max_par != -1)tree[i].max_par += lazy[i];
	if(tree[i].max_impar != -1)tree[i].max_impar +=lazy[i];

	if(lazy[i]&1)
	{
		swap(tree[i].min_par, tree[i].min_impar);
		swap(tree[i].max_par,tree[i].max_impar);
	}
	if(l != r){
		lazy[2 * i] += lazy[i];
		lazy[2 * i + 1] += lazy[i];
	}
	lazy[i] = 0;
}

void modif(int i, int l, int r, int tl, int tr, int val)
{
	push(i,l,r);
	if(l > tr || r < tl)return;

	if(l >= tl && r <= tr){
		lazy[i] += val;
		push(i,l,r);
		return;
	}
	int mid = (l + r) >> 1;

	modif(2 * i, l, mid, tl, tr, val);
	modif(2 * i + 1,mid + 1, r, tl, tr, val);

	tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}

T query(int i, int l, int r, int tl, int tr)
{
	push(i,l,r);
	if(l > tr || r < tl)return {-1,-1,-1, -1};
	if(l >= tl && r<=tr)return tree[i];
	int mid = (l + r) >> 1;

	T left = query(2 * i, l, mid, tl,tr);
	T right = query(2 * i + 1, mid + 1, r, tl,tr);
	return merge(left,right);
}
int a[maxn];
void build(int i, int l, int r)
{
	if(l==r)
	{
		if(a[l]%2==0)
		{
			tree[i].min_par = a[l];
			tree[i].max_par = a[l];
			tree[i].min_impar = -1;
			tree[i].max_impar = -1;
		}
		if(a[l]&1)
		{
			tree[i].min_par = -1;
			tree[i].max_par = -1;
			tree[i].max_impar = a[l];
			tree[i].min_impar = a[l];
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(2 * i, l,mid);
	build(2 * i + 1, mid + 1, r);
	tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}

void solve()
{
	int n, q;
	cin >> n;
	forn(i,n){
		cin >> a[i];
	}

	build(1,0,n-1);
	cin >> q;
	while(q--)
	{
		int type;
		cin >> type;
		if(type==0)
		{
			int l,r,x;
			cin >> l >> r >> x;
			--l,--r;
			modif(1,0,n-1,l,r,x);
		}

		if(type == 1)
		{
			int l,r;
			cin >> l >> r;
			--l,--r;
			T ans = query(1,0,n-1,l,r);
			cout << ans.min_par << " " << ans.max_impar << '\n';
		}
	}

}
 
int32_t main()
{
	fastio;
    int t = 1;
   	//cin >> t;
    while(t--)
    {
        solve(); 
    }
}

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