Submission #217450

#	Time	Username	Problem	Language	Result	Execution time	Memory
217450		dimash241	Simple (info1cup19_simple)	C++17	100 / 100	598 ms	39672 KiB

subway

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

//# include <ext/pb_ds/assoc_container.hpp>
//# include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 2e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
array<ll, 2> mx[N*4];
array<ll, 2> mn[N*4];
array<ll, 2> bad;

ll add[N*4];

void push (int v, int tl, int tr) {
	if(!add[v]) return;
	if(tl!=tr) {
		add[v<<1] += add[v];
		add[v<<1|1] += add[v];
	}
	for (int i = 0; i < 2; ++i) {
		if (mx[v][i] != -1) {
			mx[v][i] += add[v];
		}
		if (mn[v][i] != -1) {
			mn[v][i] += add[v];
		}
	}

	if(add[v]%2) {
		swap(mn[v][0], mn[v][1]);
		swap(mx[v][0], mx[v][1]);
	}

	add[v] = 0;
}

void upda (int p, ll x, int v = 1, int tl = 1, int tr = n) {
	push(v,tl, tr);
	if (tl > p || p > tr) return;
	if (tl == tr) {
		mx[v] = mn[v] = bad;
		mx[v][x%2] = mn[v][x%2] = x;

		return;
	}
	int tm = (tl + tr) >> 1;
	upda(p, x, v<<1, tl, tm);
	upda(p, x, v<<1|1, tm + 1, tr);
	for (int i = 0; i < 2; ++i) {
		mx[v][i] = max(mx[v<<1][i], mx[v<<1|1][i]);

		if(mn[v<<1][i] == -1)
			mn[v][i] = mn[v<<1|1][i];
		else if (mn[v<<1|1][i] == -1) {
			mn[v][i] = mn[v<<1][i];
		} else {
			mn[v][i] = min(mn[v<<1][i], mn[v<<1|1][i]);
		}
//		cout << "vertex then stats: " << v << ' ' << mx[v][i] << ' ' << mn[v][i] << '\n';
	}
}
void upd (int l, int r, ll x, int v = 1, int tl = 1, int tr = n) {
	push(v,tl, tr);
	if (tl > r || l > tr) return;
	if (tl >= l && tr <= r) {
		add[v] += x;
		push(v, tl, tr);
		return;
	}

	int tm = (tl + tr) >> 1;
	upd(l, r, x, v<<1, tl, tm);
	upd(l, r, x, v<<1|1, tm + 1, tr);

	for (int i = 0; i < 2; ++i) {
		mx[v][i] = max(mx[v<<1][i], mx[v<<1|1][i]);
		if(mn[v<<1][i] == -1)
			mn[v][i] = mn[v<<1|1][i];
		else if (mn[v<<1|1][i] == -1) {
			mn[v][i] = mn[v<<1][i];
		} else {
			mn[v][i] = min(mn[v<<1][i], mn[v<<1|1][i]);
		}
	}
}

pair < array<ll, 2 >, array<ll, 2> > get (int l, int r, int v = 1, int tl = 1 ,int tr = n) {
	push(v, tl, tr);
	if (tl > r || l > tr) return {bad, bad};
	if (tl >= l && tr <= r) {
		return {mn[v], mx[v]};
	}

	int tm = (tl + tr) >> 1;
	auto a = get(l, r, v<<1, tl, tm);
	auto b = get(l, r, v<<1|1, tm + 1, tr);

	for (int i = 0; i < 2; ++i) {
		a.S[i] = max(a.S[i], b.S[i]);

		if(a.F[i] == -1)
			a.F[i] = b.F[i];
		else if (b.F[i] != -1) {
			a.F[i] = min(a.F[i], b.F[i]);
		}
	}
	return a;
}


int main () {
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < N * 4; ++j) {
			mx[j][i] = -1;
			mn[j][i] = -1;
			bad[i] = -1;
		}
	}

	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		ll x;
		scanf("%lld", &x);
		upda (i, x);
//		if(i%2==0) 
	}

	scanf("%d", &m);
	for (int i = 1, op; i <= m; ++i) {
		scanf("%d", &op);
		if (op == 0) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			upd(a, b, c);
		} else {
			int a, b;
			scanf("%d%d", &a, &b);

			auto it = get(a, b);
			printf("%lld %lld\n", it.F[0], it.S[1]); 
		} 

	}

	
	return Accepted;
}

// B...a

Compilation message (stderr)

subway.cpp: In function 'int main()':
subway.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
subway.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~
subway.cpp:174:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
subway.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
subway.cpp:179:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &a, &b, &c);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
subway.cpp:183:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~

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