oj.uz

Submission #674409

# Submission time Handle Problem Language Result Execution time Memory
674409 2022-12-24T04:35:09 Z QwertyPi Simple (info1cup19_simple) C++14
60 / 100
 1000 ms 28212 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;
			for(int j = l; j <= r; j++){
				segTree.upd(j, j, val, 0, 0, n - 1);
			}
			// 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 535 ms 6888 KB Output is correct
2 Correct 559 ms 6992 KB Output is correct
3 Correct 888 ms 7472 KB Output is correct
4 Correct 352 ms 7256 KB Output is correct
5 Correct 568 ms 7368 KB Output is correct
6 Correct 334 ms 7244 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 17268 KB Output is correct
2 Correct 706 ms 28212 KB Output is correct
3 Correct 696 ms 28036 KB Output is correct
4 Correct 724 ms 27936 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 6888 KB Output is correct
2 Correct 559 ms 6992 KB Output is correct
3 Correct 888 ms 7472 KB Output is correct
4 Correct 352 ms 7256 KB Output is correct
5 Correct 568 ms 7368 KB Output is correct
6 Correct 334 ms 7244 KB Output is correct
7 Correct 345 ms 17268 KB Output is correct
8 Correct 706 ms 28212 KB Output is correct
9 Correct 696 ms 28036 KB Output is correct
10 Correct 724 ms 27936 KB Output is correct
11 Execution timed out 1085 ms 16740 KB Time limit exceeded
12 Halted 0 ms 0 KB -