Submission #832491

#	Time	Username	Problem	Language	Result	Execution time	Memory
832491		rainboy	ZIGZAG (INOI20_zigzag)	C11	100 / 100	1276 ms	52016 KiB

Main

#include <stdio.h>

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */

int sgn(long long a) { return a == 0 ? 0 : (a < 0 ? -1 : 1); }

int h_, n_;

int aa_[N_ * 2]; long long bb_[N_ * 2];

void put(int i, int a, long long b) {
	aa_[i] *= a, bb_[i] = bb_[i] * a + b;
}

void pus(int i) {
	if (aa_[i] != 1 || bb_[i] != 0)
		put(i << 1 | 0, aa_[i], bb_[i]), put(i << 1 | 1, aa_[i], bb_[i]), aa_[i] = 1, bb_[i] = 0;
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

int sz[N_ * 2], pppos[N_ * 2], ppneg[N_ * 2], qqpos[N_ * 2], qqneg[N_ * 2]; long long st[N_ * 2]; char lz[N_];

void put_(int i) {
	int tmp;

	tmp = pppos[i], pppos[i] = ppneg[i], ppneg[i] = tmp;
	tmp = qqpos[i], qqpos[i] = qqneg[i], qqneg[i] = tmp;
	if (i < n_)
		lz[i] ^= 1;
}

void pus_(int i) {
	if (lz[i])
		put_(i << 1 | 0), put_(i << 1 | 1), lz[i] = 0;
}

void pul_(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1;

		pppos[i] = pppos[l] < sz[l] ? pppos[l] : sz[l] + pppos[r];
		ppneg[i] = ppneg[l] < sz[l] ? ppneg[l] : sz[l] + ppneg[r];
		qqpos[i] = qqpos[r] < sz[r] ? qqpos[r] : qqpos[l] + sz[r];
		qqneg[i] = qqneg[r] < sz[r] ? qqneg[r] : qqneg[l] + sz[r];
		st[i] = st[l] + st[r] + (long long) qqpos[l] * pppos[r] + (long long) qqneg[l] * ppneg[r];
	}
}

void push_(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus_(i >> h);
}

void pull_(int i) {
	while (i > 1)
		pul_(i >>= 1);
}

void build(int *aa, int n) {
	int i, x;

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++)
		aa_[i] = 1, bb_[i] = 0;
	for (i = 0; i < n_; i++)
		aa_[n_ + i] = 0, bb_[n_ + i] = i < n ? aa[i] : 0;
	for (i = 0; i < n_; i++) {
		sz[n_ + i] = 1;
		x = i + 1 < n ? sgn(aa[i + 1] - aa[i]) * (i % 2 == 0 ? 1 : -1) : 0;
		if (x == 1)
			pppos[n_ + i] = 1, ppneg[n_ + i] = 0, qqpos[n_ + i] = 1, qqneg[n_ + i] = 0, st[n_ + i] = 1;
		else if (x == -1)
			pppos[n_ + i] = 0, ppneg[n_ + i] = 1, qqpos[n_ + i] = 0, qqneg[n_ + i] = 1, st[n_ + i] = 1;
		else
			pppos[n_ + i] = 0, ppneg[n_ + i] = 0, qqpos[n_ + i] = 0, qqneg[n_ + i] = 0, st[n_ + i] = 0;
	}
	for (i = n_ - 1; i > 0; i--)
		sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1], pul_(i);
}

void update(int l, int r, int a, long long b) {
	push(l += n_), push(r += n_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, a, b);
		if ((r & 1) == 0)
			put(r--, a, b);
	}
}

long long query(int i) {
	push(i += n_);
	return bb_[i];
}

void upd_(int i, int x) {
	i += n_;
	push_(i);
	if (x == 1)
		pppos[i] = 1, ppneg[i] = 0, qqpos[i] = 1, qqneg[i] = 0, st[i] = 1;
	else if (x == -1)
		pppos[i] = 0, ppneg[i] = 1, qqpos[i] = 0, qqneg[i] = 1, st[i] = 1;
	else
		pppos[i] = 0, ppneg[i] = 0, qqpos[i] = 0, qqneg[i] = 0, st[i] = 0;
	pull_(i);
}

void update_(int l, int r) {
	int l_, r_;

	if (l > r)
		return;
	l_ = l += n_, r_ = r += n_;
	push_(l_), push_(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put_(l++);
		if ((r & 1) == 0)
			put_(r--);
	}
	pull_(l_), pull_(r_);
}

long long query_(int l, int r) {
	int qpos, qneg, ppos, pneg;
	long long x;

	if (l > r)
		return 0;
	push_(l += n_), push_(r += n_);
	qpos = 0, qneg = 0, ppos = 0, pneg = 0, x = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			x += st[l] + (long long) qpos * pppos[l] + (long long) qneg * ppneg[l];
			qpos = qqpos[l] < sz[l] ? qqpos[l] : qpos + sz[l];
			qneg = qqneg[l] < sz[l] ? qqneg[l] : qneg + sz[l];
			l++;
		}
		if ((r & 1) == 0) {
			x += st[r] + (long long) qqpos[r] * ppos + (long long) qqneg[r] * pneg;
			ppos = pppos[r] < sz[r] ? pppos[r] : sz[r] + ppos;
			pneg = ppneg[r] < sz[r] ? ppneg[r] : sz[r] + pneg;
			r--;
		}
	}
	x += (long long) qpos * ppos + (long long) qneg * pneg;
	return x;
}

int main() {
	static int aa[N];
	int n, q, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	build(aa, n);
	while (q--) {
		static char s[2];
		int l, r, x;

		scanf("%s%d%d", s, &l, &r), l--, r--;
		if (s[0] == '*') {
			update(l, r, -1, 0);
			if (l > 0)
				upd_(l - 1, sgn(query(l) - query(l - 1)) * ((l - 1) % 2 == 0 ? 1 : -1));
			update_(l, r - 1);
			if (r + 1 < n)
				upd_(r, sgn(query(r + 1) - query(r)) * (r % 2 == 0 ? 1 : -1));
		} else if (s[0] == '+') {
			scanf("%d", &x);
			update(l, r, 1, x);
			if (l > 0)
				upd_(l - 1, sgn(query(l) - query(l - 1)) * ((l - 1) % 2 == 0 ? 1 : -1));
			if (r + 1 < n)
				upd_(r, sgn(query(r + 1) - query(r)) * (r % 2 == 0 ? 1 : -1));
		} else
			printf("%lld\n", query_(l, r - 1) + r - l + 1);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:166:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:168:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:174:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |   scanf("%s%d%d", s, &l, &r), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:183:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |    scanf("%d", &x);
      |    ^~~~~~~~~~~~~~~

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