Submission #583406

#	Time	Username	Problem	Language	Result	Execution time	Memory
583406		GioChkhaidze	ZIGZAG (INOI20_zigzag)	C++14	100 / 100	968 ms	89292 KiB

Main

#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
#define int 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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15