oj.uz

Submission #674410

# Submission time Handle Problem Language Result Execution time Memory
674410 2022-12-24T04:36:03 Z QwertyPi Simple (info1cup19_simple) C++14
100 / 100
 700 ms 34764 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6868 KB Output is correct
2 Correct 13 ms 6900 KB Output is correct
3 Correct 15 ms 7124 KB Output is correct
4 Correct 16 ms 7128 KB Output is correct
5 Correct 16 ms 7124 KB Output is correct
6 Correct 17 ms 7140 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 17272 KB Output is correct
2 Correct 697 ms 27960 KB Output is correct
3 Correct 700 ms 28036 KB Output is correct
4 Correct 696 ms 27916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6868 KB Output is correct
2 Correct 13 ms 6900 KB Output is correct
3 Correct 15 ms 7124 KB Output is correct
4 Correct 16 ms 7128 KB Output is correct
5 Correct 16 ms 7124 KB Output is correct
6 Correct 17 ms 7140 KB Output is correct
7 Correct 345 ms 17272 KB Output is correct
8 Correct 697 ms 27960 KB Output is correct
9 Correct 700 ms 28036 KB Output is correct
10 Correct 696 ms 27916 KB Output is correct
11 Correct 320 ms 18920 KB Output is correct
12 Correct 652 ms 33516 KB Output is correct
13 Correct 689 ms 34296 KB Output is correct
14 Correct 645 ms 33492 KB Output is correct
15 Correct 693 ms 34764 KB Output is correct
16 Correct 268 ms 30896 KB Output is correct