oj.uz

Submission #217450

# Submission time Handle Problem Language Result Execution time Memory
217450 2020-03-29T17:54:46 Z dimash241 Simple (info1cup19_simple) C++17
100 / 100
 598 ms 39672 KB 
//#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25464 KB Output is correct
2 Correct 26 ms 25600 KB Output is correct
3 Correct 28 ms 25728 KB Output is correct
4 Correct 29 ms 25728 KB Output is correct
5 Correct 27 ms 25728 KB Output is correct
6 Correct 27 ms 25728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 29560 KB Output is correct
2 Correct 490 ms 34040 KB Output is correct
3 Correct 488 ms 34040 KB Output is correct
4 Correct 468 ms 33916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25464 KB Output is correct
2 Correct 26 ms 25600 KB Output is correct
3 Correct 28 ms 25728 KB Output is correct
4 Correct 29 ms 25728 KB Output is correct
5 Correct 27 ms 25728 KB Output is correct
6 Correct 27 ms 25728 KB Output is correct
7 Correct 229 ms 29560 KB Output is correct
8 Correct 490 ms 34040 KB Output is correct
9 Correct 488 ms 34040 KB Output is correct
10 Correct 468 ms 33916 KB Output is correct
11 Correct 267 ms 32124 KB Output is correct
12 Correct 590 ms 38648 KB Output is correct
13 Correct 552 ms 39416 KB Output is correct
14 Correct 598 ms 38520 KB Output is correct
15 Correct 533 ms 39672 KB Output is correct
16 Correct 213 ms 31836 KB Output is correct