Submission #834309

#	Time	Username	Problem	Language	Result	Execution time	Memory
834309		rainboy	Progression (NOI20_progression)	C11	48 / 100	600 ms	60744 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 kk[N_ * 2];
long long aap[N_ * 2]; int kkp[N_ * 2];
long long aaq[N_ * 2]; int kkq[N_ * 2];
int kk_[N_ * 2];
int lz[N_];
int h_, n_;

void put(int i, long long x) {
	aap[i] += x, aaq[i] += x;
	if (i < n_)
		lz[i] += x;
}

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

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

		aap[i] = aap[l], kkp[i] = kkp[l] < kk[l] || aap[l] != aap[r] ? kkp[l] : kk[l] + kkp[r];
		aaq[i] = aaq[r], kkq[i] = kkq[r] < kk[r] || aaq[l] != aaq[r] ? kkq[r] : kkq[l] + kk[r];
		kk_[i] = max(kk_[l], kk_[r]);
		if (aaq[l] == aap[r])
			kk_[i] = max(kk_[i], kkq[l] + kkp[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;

	h_ = 0;
	while (1 << h_ < n - 1)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i + 1 < n; i++) {
		kk[n_ + i] = 1;
		aap[n_ + i] = aaq[n_ + i] = aa[i + 1] - aa[i], kkp[n_ + i] = kkq[n_ + i] = kk_[n_ + i] = 1;
	}
	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, long long x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

int query(int l, int r) {
	long long aq, ap;
	int kq, kp, k_;

	push(l += n_), push(r += n_);
	aq = 0, kq = 0, ap = 0, kp = 0, k_ = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			k_ = max(k_, kk_[l]);
			if (aq == aap[l])
				k_ = max(k_, kq + kkp[l]);
			kq = kkq[l] < kk[l] || aq != aaq[l] ? kkq[l] : kq + kkq[l], aq = aaq[l];
			l++;
		}
		if ((r & 1) == 0) {
			k_ = max(kk_[r], k_);
			if (aaq[r] == ap)
				k_ = max(k_, kkq[r] + kp);
			kp = kkp[r] < kk[r] || aap[r] != ap ? kkp[r] : kkp[r] + kp, ap = aap[r];
			r--;
		}
	}
	if (aq == ap)
		k_ = max(k_, kq + kp);
	return k_;
}

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--) {
		int t, l, r, a, b;

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

Compilation message (stderr)

Progression.c: In function 'main':
Progression.c:109:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Progression.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Progression.c:116:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   scanf("%d%d%d", &t, &l, &r), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.c:118:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |    scanf("%d%d", &b, &a);
      |    ^~~~~~~~~~~~~~~~~~~~~

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