oj.uz

Submission #583405

# Submission time Handle Problem Language Result Execution time Memory
583405 2022-06-25T10:25:54 Z GioChkhaidze ZIGZAG (INOI20_zigzag) C++14
8 / 100
 722 ms 70212 KB 
#include <bits/stdc++.h>
 
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
 
using namespace std;
 
const int N = 3e5 + 5;

int n, m, q, L, R, id;
ll vl, a[N], b[N], vd[4 * N];
bool dv[4 * N], tp;

struct node {
	ll ans;
	int pr;
	int sf;
	ll fr;
	ll ls;
	int len;
	bool add;

	node() {
		ans = 0;
		pr = 0;
		sf = 0;
		fr = 0;
		ls = 0;
		len = 0;
		add = 0;
	}
};
 
node v[4 * N], bs;
node mrg(node a, node b) {
	node c;
	c.add = 0;
	c.len = a.len + b.len;
	c.ans = a.ans + b.ans;
	c.fr = a.fr, c.ls = b.ls;
	c.sf = b.sf, c.pr = a.pr;
	if ((a.ls < 0 && b.fr > 0) || (a.ls > 0 && b.fr < 0)) {
		if (b.sf == b.len) c.sf += a.sf;
		if (a.pr == a.len) c.pr += b.pr;	
		c.ans += a.sf * b.pr;
	}
	return c;
}
 
void build(tree) {
	if (l > r) return ;
	if (l == r) {
		v[h].add = 0;
		v[h].len = 1;
		v[h].fr = b[l];
		v[h].ls = b[l];
		if (v[h].fr) {
			v[h].pr = v[h].sf = v[h].ans = 1;
		}
			else {
			v[h].pr = v[h].sf = v[h].ans = 0;
		}
		return ;
	}
	build(left), build(right);
	v[h] = mrg(v[lf], v[rf]);
}
 
void shift(tree) {
	if (v[h].add) {
		v[lf].add ^= 1, v[lf].fr *= -1; v[lf].ls *= -1;
		v[rf].add ^= 1, v[rf].fr *= -1; v[rf].ls *= -1;
		v[h].add = 0;
		return ;
	}
}
 
node get(tree) {
	if (r < L || R < l) return bs;
	if (L <= l && r <= R) return v[h];
	shift(h, l, r);
	return mrg(get(left), get(right));
}
 
void upd(tree) {
	if (r < id || id < l) return ;
	if (l == id && id == r) {
		v[h].fr += vl; 
		v[h].ls += vl;
		if (v[h].fr) {
			v[h].pr = v[h].sf = v[h].ans = 1;
		}
			else {
			v[h].pr = v[h].sf = v[h].ans = 0;
		}
		return ;
	}
	shift(h, l, r);
	upd(left), upd(right);
	v[h] = mrg(v[lf], v[rf]);
}
 
void upd_(tree) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		v[h].add ^= 1;
		v[h].fr *= -1;
		v[h].ls *= -1;
		return ;
	}
	shift(h, l, r);
	upd_(left), upd_(right);
	v[h] = mrg(v[lf], v[rf]);
}
 
void bld(tree) {
	if (l == r) { vd[h] = a[l]; return ; }
	bld(left); bld(right);
}
 
void shf(tree) {
	if (dv[h]) {
		vd[lf] = vd[lf] * -1 + vd[h];
		vd[rf] = vd[rf] * -1 + vd[h];
		dv[lf] ^= 1, dv[rf] ^= 1;
	}
		else {
		vd[lf] += vd[h];
		vd[rf] += vd[h];
	}
	vd[h] = dv[h] = 0;
	return ;
}
 
void up(tree) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		if (tp == 0) {
			vd[h] += vl;
		}
			else
		if (tp == 1) {
			vd[h] *= -1;  
			dv[h] ^= 1;
		}
		return ;
	}
	shf(h, l, r);
	up(left), up(right);
} 
 
ll G(tree) {
	if (l == r) return vd[h];
	shf(h, l, r);
	if (id <= mf) 
		return G(left);
	return G(right);
}
 
main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (1 < i) {
			b[i - 1] = a[i - 1] - a[i];
		}
	}
 
	m = n - 1, build(1, 1, m), bld(1, 1, n);
	for (int i = 1; i <= q; ++i) {
		char c;
		cin >> c;
		if (c == '+') {
			cin >> L >> R >> vl; tp = 0, up(1, 1, n), --L;
			vl = -vl, id = L; if (1 <= L) upd(1, 1, m);
			vl = -vl, id = R; if (R <= m) upd(1, 1, m);
		}
			else
		if (c == '*') {
			vl = 0;
			cin >> L >> R; 
			if (1 < L) {
				id = L;
				ll Al = G(1, 1, n);
				id = L - 1;
				vl = 2 * Al;
				upd(1, 1, m);
			}
			if (R < n) { 
				id = R;
				ll Ar = G(1, 1, n);
				vl = -2 * Ar;
				upd(1, 1, m);
			}
			
			tp = 1, up(1, 1, n);
			--R, upd_(1, 1, m);
		}
			else 
		if (c == '?') {
			cin >> L >> R; --R;
			cout << get(1, 1, m).ans + R - L + 2 << "\n";
		}
	}
}

Compilation message

Main.cpp:165:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  165 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47436 KB Output is correct
2 Correct 32 ms 47472 KB Output is correct
3 Correct 31 ms 47528 KB Output is correct
4 Correct 29 ms 47516 KB Output is correct
5 Correct 28 ms 47532 KB Output is correct
6 Correct 21 ms 47320 KB Output is correct
7 Correct 25 ms 47444 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 62268 KB Output is correct
2 Correct 96 ms 49484 KB Output is correct
3 Correct 594 ms 70068 KB Output is correct
4 Correct 722 ms 70212 KB Output is correct
5 Correct 676 ms 70140 KB Output is correct
6 Correct 657 ms 70124 KB Output is correct
7 Incorrect 665 ms 66952 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47436 KB Output is correct
2 Correct 32 ms 47472 KB Output is correct
3 Correct 31 ms 47528 KB Output is correct
4 Correct 29 ms 47516 KB Output is correct
5 Correct 28 ms 47532 KB Output is correct
6 Correct 21 ms 47320 KB Output is correct
7 Correct 25 ms 47444 KB Output is correct
8 Correct 237 ms 52116 KB Output is correct
9 Correct 238 ms 53052 KB Output is correct
10 Correct 249 ms 54068 KB Output is correct
11 Correct 146 ms 53236 KB Output is correct
12 Correct 253 ms 54020 KB Output is correct
13 Correct 247 ms 54016 KB Output is correct
14 Correct 236 ms 54056 KB Output is correct
15 Correct 254 ms 53008 KB Output is correct
16 Correct 260 ms 54016 KB Output is correct
17 Correct 225 ms 54160 KB Output is correct
18 Incorrect 151 ms 53968 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47436 KB Output is correct
2 Correct 32 ms 47472 KB Output is correct
3 Correct 31 ms 47528 KB Output is correct
4 Correct 29 ms 47516 KB Output is correct
5 Correct 28 ms 47532 KB Output is correct
6 Correct 21 ms 47320 KB Output is correct
7 Correct 25 ms 47444 KB Output is correct
8 Correct 703 ms 62268 KB Output is correct
9 Correct 96 ms 49484 KB Output is correct
10 Correct 594 ms 70068 KB Output is correct
11 Correct 722 ms 70212 KB Output is correct
12 Correct 676 ms 70140 KB Output is correct
13 Correct 657 ms 70124 KB Output is correct
14 Incorrect 665 ms 66952 KB Output isn't correct
15 Halted 0 ms 0 KB -