oj.uz

Submission #365566

# Submission time Handle Problem Language Result Execution time Memory
365566 2021-02-11T21:03:47 Z SlavicG Simple (info1cup19_simple) C++14
100 / 100
 577 ms 32748 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 748 KB Output is correct
2 Correct 7 ms 876 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 8 ms 1260 KB Output is correct
6 Correct 8 ms 1260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 11116 KB Output is correct
2 Correct 429 ms 21868 KB Output is correct
3 Correct 416 ms 21996 KB Output is correct
4 Correct 410 ms 21868 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 748 KB Output is correct
2 Correct 7 ms 876 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 8 ms 1260 KB Output is correct
6 Correct 8 ms 1260 KB Output is correct
7 Correct 184 ms 11116 KB Output is correct
8 Correct 429 ms 21868 KB Output is correct
9 Correct 416 ms 21996 KB Output is correct
10 Correct 410 ms 21868 KB Output is correct
11 Correct 241 ms 16072 KB Output is correct
12 Correct 562 ms 31596 KB Output is correct
13 Correct 514 ms 32236 KB Output is correct
14 Correct 577 ms 31596 KB Output is correct
15 Correct 487 ms 32748 KB Output is correct
16 Correct 120 ms 24812 KB Output is correct