oj.uz

Submission #674407

# Submission time Handle Problem Language Result Execution time Memory
674407 2022-12-24T04:04:16 Z QwertyPi Simple (info1cup19_simple) C++14
30 / 100
 700 ms 33072 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];
		t[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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 19688 KB Output is correct
2 Correct 700 ms 33000 KB Output is correct
3 Correct 695 ms 33072 KB Output is correct
4 Correct 693 ms 32992 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -