Submission #1318441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318441		muhammad-ahmad	Simple (info1cup19_simple)	C++20	100 / 100	328 ms	31388 KiB

subway

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io() {
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 2e5 + 5;
int n, q, a[N];

struct node {
	int val = 0, Omi = 1e18, Oma = -1e18, Emi = 1e18, Ema = -1e18, lazy = 0;
} T[4 * N];

node join(node a, node b){
	node c;
	c.Omi = min(a.Omi, b.Omi);
	c.Emi = min(a.Emi, b.Emi);
	c.Ema = max(a.Ema, b.Ema);
	c.Oma = max(a.Oma, b.Oma);
	return c;
}

pair<int, int> combine(pair<int, int> a, pair<int, int> b){
	pair<int, int> c;
	c.fi = min(a.fi, b.fi);
	c.se = max(a.se, b.se);
	return c;
} 

void apply(node &a, int x){
	a.Omi += x, a.Oma += x, a.Emi += x, a.Ema += x;
	a.lazy += x;
	if (x % 2){
		swap(a.Omi, a.Emi);
		swap(a.Oma, a.Ema);
	}
}

void push(int v){
	int lc = 2 * v, rc = lc + 1, x = T[v].lazy;
	apply(T[lc], x);
	apply(T[rc], x);
	T[v].lazy = 0;
	return;
}

void build (int v = 1, int s = 1, int e = n + 1){
	if (e - s == 1){
		if (a[s] % 2){
			T[v].Omi = a[s];
			T[v].Oma = a[s];
			T[v].Emi = 1e18;
			T[v].Ema = -1e18;
		}
		else {
			T[v].Emi = a[s];
			T[v].Ema = a[s];
			T[v].Omi = 1e18;
			T[v].Oma = -1e18;
		}
		T[v].val = 0;
		return;
	}
	int lc = 2 * v, rc = lc + 1, mid = (s + e) / 2;
	build(lc, s, mid);
	build(rc, mid, e);
	T[v] = join(T[lc], T[rc]);
}

void upd(int x, int l, int r, int v = 1, int s = 1, int e = n + 1){
	if (e <= l or r <= s) return;
	if (l <= s && e <= r){
		apply(T[v], x);
		return;
	}
	
	push(v);
	int lc = 2 * v, rc = lc + 1, mid = (s + e) / 2;
	upd(x, l, r, lc, s, mid);
	upd(x, l, r, rc, mid, e);
	
	T[v] = join(T[lc], T[rc]);
}

pair<int, int> query(int l, int r, int v = 1, int s = 1, int e = n + 1){
	if (e <= l or r <= s) return {1e18, -1e18};
	if (l <= s && e <= r){
		if (s == 4 && e == 5){
		}
		return {T[v].Emi, T[v].Oma};
	}
	// cout << s << ' ' << e << endl;
	push(v);
	int lc = 2 * v, rc = lc + 1, mid = (s + e) / 2;
	if (mid < r){
		pair<int, int> ans = query(l, r, rc, mid, e);
		if (l < mid){
			ans = combine(ans, query(l, r, lc, s, mid));
		}
		return ans;
	}
	else return query(l, r, lc, s, mid);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build();
	cin >> q;
	for (int Q = 1; Q <= q; Q++){
		int t; cin >> t;
		int l, r, v;
		if (t == 0){
			cin >> l >> r >> v;
			upd(v, l, r + 1);
		}
		else {
			cin >> l >> r;
			pair<int, int> A = query(l, r + 1);
			if (A.fi > 1e17) A.fi = -1;
			if (A.se < -1e17) A.se = -1;
			cout << A.fi << ' ' << A.se << endl;
		}
	}
	// cout << query(2, 4).se << endl;
}

signed main() {
	fast_io();
	srand(chrono::steady_clock::now().time_since_epoch().count());
	int tc = 1;
	// cin >> tc;
	while (tc--) solve();
	return 0;
}

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