Submission #583314

#	Time	Username	Problem	Language	Result	Execution time	Memory
583314		GioChkhaidze	ZIGZAG (INOI20_zigzag)	C++14	0 / 100	2073 ms	62416 KiB

Main

// Source: https://usaco.guide/general/io

#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, a[N];
int L, R, id;
ll vl, b[N];

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

node v[4 * N], bs = {0, 0, 0, 0, 0, 0, 0};

node merge(node a, node b) {
	node c;
	c.add = 0;
	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) {
		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;
		}
		return ;
	}
	build(left), build(right);
	v[h] = merge(v[lf], v[rf]);
	v[h].len = v[lf].len + v[rf].len;
}

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 merge(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] = merge(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] = merge(v[lf], v[rf]);
}

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);
	for (int i = 1; i <= q; ++i) {
		char c;
		cin >> c;
		if (c == '+') {
			cin >> L >> R >> vl; --L;
			vl = -vl, id = L; if (1 <= L) upd(1, 1, m), b[id] += vl;
			vl = -vl, id = R; if (R <= m) upd(1, 1, m), b[id] += vl;
		}
			else
		if (c == '*') {
			vl = 0;
			cin >> L >> R; --R;
			for (int j = L; j <= R; ++j) {
				b[j] *= -1;
			}

			build(1, 1, m);
			/*
			upd_(1, 1, m); ++R, --L;
			id = L; if (1 <= L) upd(1, 1, m);
			id = R; if (R <= m) upd(1, 1, m);*/
		}
			else 
		if (c == '?') {
			cin >> L >> R; --R;
			
			ll res = R - L + 2; 
			for (int j = L; j <= R; ++j) {
				for (int k = j; k <= R; ++k) {
					if ((k == j && b[k]) || (b[k - 1] > 0 && b[k] < 0) || (b[k - 1] < 0 && b[k] > 0)) {
						++res;
					}
				}
			}
			
			cout << res << "\n";
			//cout << get(1, 1, m).ans + R - L + 2 << "\n";
		}
	}
}

Compilation message (stderr)

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

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