Submission #1127174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127174		abushbandit_	Simple (info1cup19_simple)	C++20	100 / 100	309 ms	27180 KiB

subway

//~ how can i make it 10% more fun?
//~ what it would take for me to enjoy this?

#include <bits/stdc++.h>

using namespace std;
 
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
int exp(int x, int n, int m) {
	x %= m;
	int res = 1;
	while (n > 0) {
		if (n & 1) { res = (res * x) % m; }
		x = (x * x) % m;
		n >>= 1;
	}
	return res;
}
 
int power(int x, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) { res = res * x ; }
		x = x * x ;
		n >>= 1;
	}
	return res;
}
 
const int N = 2e5 + 1;
 
const int mod = 1e9 + 7;
 
const int inf = 1e18;
 
void add(int &a, int b) {
    if (a + b >= mod) a = (a + b) - mod;
    else a += b;
}
 
void sub(int &a, int b) {
    if (a - b < 0) a = (a - b) + mod;
    else a -= b;;
}
 
template<typename T> using matrix = vector<vector<T>>;
 
namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }
 
    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }
 
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
		for (T &i: a) cin >> i;
        return cin;
    }
	
    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
 
    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }
 
    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

struct tree {
	int oddmax = -1, evenmin = inf, oddmin = inf, evenmax = -1;
};

tree t[N * 4];
int a[N], lazy[N * 4];
int n;

void push(int v, int tl, int tr) {
	
	if(!lazy[v]) return;
	
	if(tl != tr) {
		lazy[v * 2] += lazy[v];
		lazy[v * 2 + 1] += lazy[v];
	}
	
	if(lazy[v] & 1) {
		swap(t[v].evenmin, t[v].oddmin);
		swap(t[v].evenmax, t[v].oddmax);
		if(t[v].oddmax != -1)
			t[v].oddmax += lazy[v];
		if(t[v].evenmin != inf)
			t[v].evenmin += lazy[v];
		if(t[v].evenmax != -1)
			t[v].evenmax += lazy[v];
		if(t[v].oddmin != inf)
			t[v].oddmin += lazy[v];
	} else {
		if(t[v].oddmax != -1)
			t[v].oddmax += lazy[v];
		if(t[v].evenmin != inf)
			t[v].evenmin += lazy[v];
		if(t[v].evenmax != -1)
			t[v].evenmax += lazy[v];
		if(t[v].oddmin != inf)
			t[v].oddmin += lazy[v];
	}
	
	lazy[v] = 0;
	
};

tree comb(tree a, tree b) {
	
	tree c;
	c.oddmax = max(a.oddmax, b.oddmax);
	c.evenmin = min(a.evenmin, b.evenmin);
	c.oddmin = min(a.oddmin, b.oddmin);
	c.evenmax = max(a.evenmax, b.evenmax);
	return c;
	
};

void build(int v = 1, int tl = 1, int tr = n) {
	
	if(tl == tr) {
		if(a[tl] & 1) t[v].oddmin = a[tl], t[v].oddmax = a[tl];
		else t[v].evenmin = t[v].evenmax = a[tl];
	}
	else {
		int tm = (tl + tr) >> 1;
		build(v * 2, tl, tm);
		build(v * 2 + 1, tm + 1, tr);
		t[v] = comb(t[v * 2], t[v * 2 + 1]);
	}
	
}

void update (int v, int tl, int tr, int l, int r, int x) {
	
	push(v, tl, tr);
	
	if(l <= tl && tr <= r) {
		lazy[v] += x;
		push(v, tl, tr);
		return;
	}
	if(l > tr || tl > r) return;
	
	int tm = (tl + tr) >> 1;
	update(v * 2, tl, tm, l, r, x);
	update(v * 2 + 1, tm + 1, tr, l, r, x);
	t[v] = comb(t[v * 2], t[v * 2 + 1]);
	
};

tree empt;

tree get (int v, int tl, int tr, int l, int r) {
	
	push(v, tl, tr);
	
	if(l <= tl && tr <= r) {
		return t[v];
	}
	if(l > tr || tl > r) return empt;
	
	int tm = (tl + tr) >> 1;
	
	return comb(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
};

void solve() {
	
	//~ int n;
	cin >> n;
	
	for(int i = 1;i <= n;i++) cin >> a[i];
	
	build();
	
	int q;
	cin >> q;
	while(q--) {
		int type;
		cin >> type;
		if(type == 0) {
			int l, r, x;
			cin >> l >> r >> x;
			update(1, 1, n, l, r, x);
		} else {
			int l, r;
			cin >> l >> r;
			tree res = get(1, 1, n, l, r);
			if(res.evenmin == inf) res.evenmin = -1;
			cout << res.evenmin << " " << res.oddmax << "\n";
		}
	}
	
	
} 

signed main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
	
} 

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