Submission #674410

#	Time	Username	Problem	Language	Result	Execution time	Memory
674410		QwertyPi	Simple (info1cup19_simple)	C++14	100 / 100	700 ms	34764 KiB

subway

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e5 + 11;

struct node{
	int mx[2], mn[2];
	node() = default;
	node(int x){
		mx[0] = mx[1] = mn[0] = mn[1] = -1;
		mx[x % 2] = mn[x % 2] = x;
	}

	node operator+ (const node& o) const {
		if(mx[0] == -2 || o.mx[0] == -2) return mx[0] == -2 ? o : *this;
		node ret;
		for(int i = 0; i < 2; i++){
			if(mx[i] == -1 || o.mx[i] == -1) ret.mx[i] = mx[i] == -1 ? o.mx[i] : mx[i];
			else ret.mx[i] = max(mx[i], o.mx[i]);

			if(mn[i] == -1 || o.mn[i] == -1) ret.mn[i] = mn[i] == -1 ? o.mn[i] : mn[i];
			else ret.mn[i] = min(mn[i], o.mn[i]);
		}
		return ret;
	}

	void operator+= (int val) {
		if(val % 2){
			swap(mx[0], mx[1]);
			swap(mn[0], mn[1]);
		}
		for(int i = 0; i < 2; i++){
			mx[i] = mx[i] == -1 ? -1 : mx[i] + val;
			mn[i] = mn[i] == -1 ? -1 : mn[i] + val;
		}
	}
};

struct SegTree{
	node t[MAXN << 2]; int lz[MAXN << 2] = {0};
	void build(int* a, int v, int l, int r){
		if(l == r) t[v] = node(a[l]);
		else build(a, v * 2 + 1, l, (l + r) / 2), 
			 build(a, v * 2 + 2, (l + r) / 2 + 1, r),
			 t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}
	
	void push(int v){
		t[v * 2 + 1] += lz[v];
		lz[v * 2 + 1] += lz[v];
		t[v * 2 + 2] += lz[v];
		lz[v * 2 + 2] += lz[v];
		lz[v] = 0;
	}
	
	void upd(int ql, int qr, int val, int v, int l, int r){
		if(r < ql || qr < l) return;
		if(ql <= l && r <= qr){
			t[v] += val;
			lz[v] += val;
			return;
		}
		push(v);
		int m = (l + r) / 2;
		upd(ql, qr, val, v * 2 + 1, l, m);
		upd(ql, qr, val, v * 2 + 2, m + 1, r);
		t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}

	node qry(int ql, int qr, int v, int l, int r){
		if(r < ql || qr < l) return node(-2);
		if(ql <= l && r <= qr) return t[v];
		push(v);
		int m = (l + r) / 2;
		node a = qry(ql, qr, v * 2 + 1, l, m);
		node b = qry(ql, qr, v * 2 + 2, m + 1, r);
		return a + b;
	}
	
} segTree;

int a[MAXN];

int32_t main(){
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	segTree.build(a, 0, 0, n - 1);
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int ty, l, r; cin >> ty >> l >> r; l--; r--;
		if(ty == 0){
			int val; cin >> val;
			segTree.upd(l, r, val, 0, 0, n - 1);
		}else{
			node ans = segTree.qry(l, r, 0, 0, n - 1);
			cout << ans.mn[0] << ' ' << ans.mx[1] << endl;
		}
	}
}

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