Submission #834698

#	Time	Username	Problem	Language	Result	Execution time	Memory
834698		rainboy	Progression (NOI20_progression)	C11	100 / 100	751 ms	43464 KiB

Progression

#include <stdio.h>

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

int max(int a, int b) { return a > b ? a : b; }

int h_, n_;

char tt[N_ * 2]; long long aa[N_ * 2], bb[N_ * 2];

void put(int i, int t, long long a, long long b) {
	if (t == 1) {
		if (tt[i] == 0)
			tt[i] = 1;
		aa[i] += a, bb[i] += b;
	} else
		tt[i] = 2, aa[i] = a, bb[i] = b;
}

void pus(int i) {
	if (tt[i]) {
		put(i << 1 | 0, tt[i], aa[i], bb[i]), put(i << 1 | 1, tt[i], aa[i], bb[i]), tt[i] = aa[i] = bb[i] = 0;
	}
}

void push(int i) {
	int h;

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

int kk[N_ * 2], pp[N_ * 2], qq[N_ * 2], mx[N_ * 2]; char lz_[N_];

void put_(int i) {
	pp[i] = qq[i] = mx[i] = kk[i];
	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;

		pp[i] = pp[l] < kk[l] ? pp[l] : kk[l] + pp[r];
		qq[i] = qq[r] < kk[r] ? qq[r] : qq[l] + kk[r];
		mx[i] = max(max(mx[l], mx[r]), qq[l] + pp[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(long long *xx, int n) {
	int i;

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++) {
		tt[n_ + i] = 2, aa[n_ + i] = 0, bb[n_ + i] = i < n ? xx[i] : 0;
		kk[n_ + i] = 1;
		pp[n_ + i] = qq[n_ + i] = mx[n_ + i] = i + 2 < n && xx[i + 2] - xx[i + 1] * 2 + xx[i] == 0 ? 1 : 0;
	}
	for (i = n_ - 1; i > 0; i--)
		kk[i] = kk[i << 1 | 0] + kk[i << 1 | 1], pul_(i);
}

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

long long query(int i) {
	push(n_ + i);
	return aa[n_ + i] * i + bb[n_ + i];
}

void upd_(int i, int x) {
	i += n_;
	push_(i);
	pp[i] = qq[i] = mx[i] = x;
	pull_(i);
}

void update_(int l, int r) {
	int 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_);
}

int query_(int l, int r) {
	int q, p, x;

	push_(l += n_), push_(r += n_);
	q = p = x = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			x = max(max(x, mx[l]), q + pp[l]);
			q = qq[l] < kk[l] ? qq[l] : q + kk[l];
			l++;
		}
		if ((r & 1) == 0) { 
			x = max(max(mx[r], x), qq[r] + p);
			p = pp[r] < kk[r] ? pp[r] : kk[r] + p;
			r--;
		}
	}
	x = max(x, q + p);
	return x;
}

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

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%lld", &xx[i]);
	build(xx, n);
	while (q--) {
		int t, l, r, a, b;

		scanf("%d%d%d", &t, &l, &r), l--, r--;
		if (t == 1) {
			scanf("%d%d", &b, &a);
			update(l, r, 1, a, b - (long long) l * a);
			for (i = max(l - 2, 0); i <= l + 1 && i < n; i++)
				xx[i] = query(i);
			for (i = max(r - 1, 0); i <= r + 2 && i < n; i++)
				xx[i] = query(i);
			for (i = max(l - 2, 0); i < l && i + 2 < n; i++)
				upd_(i, xx[i + 2] - xx[i + 1] * 2 + xx[i] == 0 ? 1 : 0);
			for (i = max(r - 1, 0); i <= r && i + 2 < n; i++)
				upd_(i, xx[i + 2] - xx[i + 1] * 2 + xx[i] == 0 ? 1 : 0);
		} else if (t == 2) {
			scanf("%d%d", &b, &a);
			update(l, r, 2, a, b - (long long) l * a);
			if (r - l >= 2)
				update_(l, r - 2);
			for (i = max(l - 2, 0); i <= l + 1 && i < n; i++)
				xx[i] = query(i);
			for (i = max(r - 1, 0); i <= r + 2 && i < n; i++)
				xx[i] = query(i);
			for (i = max(l - 2, 0); i < l && i + 2 < n; i++)
				upd_(i, xx[i + 2] - xx[i + 1] * 2 + xx[i] == 0 ? 1 : 0);
			for (i = max(r - 1, 0); i <= r && i + 2 < n; i++)
				upd_(i, xx[i + 2] - xx[i + 1] * 2 + xx[i] == 0 ? 1 : 0);
		} else
			printf("%d\n", r - l < 2 ? r - l + 1 : query_(l, r - 2) + 2);
	}
	return 0;
}

Compilation message (stderr)

Progression.c: In function 'main':
Progression.c:145:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Progression.c:147:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%lld", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~
Progression.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d%d", &t, &l, &r), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.c:154:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |    scanf("%d%d", &b, &a);
      |    ^~~~~~~~~~~~~~~~~~~~~
Progression.c:165:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |    scanf("%d%d", &b, &a);
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17