oj.uz

Submission #834539

# Submission time Handle Problem Language Result Execution time Memory
834539 2023-08-22T15:20:55 Z rainboy Progression (NOI20_progression) C
50 / 100
 3000 ms 46560 KB 
#include <stdio.h>

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

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

int kk[N_ * 2];
long long ss[N_ * 2];
long long aap[N_ * 2]; int kkp[N_ * 2];
long long aaq[N_ * 2]; int kkq[N_ * 2];
int kk_[N_ * 2];
char tz[N_]; long long lz[N_];
int h_, n_;

void put(int i, int t, long long x) {
	if (t == 1) {
		ss[i] += x * kk[i], aap[i] += x, aaq[i] += x;
		if (tz[i] == 0)
			tz[i] = 1;
		if (i < n_)
			lz[i] += x;
	} else {
		ss[i] = x * kk[i];
		aap[i] = x, kkp[i] = kk[i];
		aaq[i] = x, kkq[i] = kk[i];
		kk_[i] = kk[i];
		if (i < n_)
			tz[i] = 2, lz[i] = x;
	}
}

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

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

		ss[i] = ss[l] + ss[r];
		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, a;

	h_ = 0;
	while (1 << h_ <= n + 1)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i <= n; i++) {
		a = (i == n ? 0 : aa[i]) - (i == 0 ? 0 : aa[i - 1]);
		kk[n_ + i] = 1;
		ss[n_ + i] = a;
		aap[n_ + i] = a, kkp[n_ + i] = 1;
		aaq[n_ + i] = a, kkq[n_ + i] = 1;
		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, int t, 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++, t, x);
		if ((r & 1) == 0)
			put(r--, t, x);
	}
	pull(l_), pull(r_);
}

long long query_s(int r) {
	int l;
	long long s;

	push(r += n_);
	s = 0;
	for (l = 0 + n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			s += ss[r--];
	return s;
}

int query_k_(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;
		long long dl, dr;

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

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 41020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 472 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 476 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 37720 KB Output is correct
2 Correct 106 ms 2992 KB Output is correct
3 Correct 85 ms 2944 KB Output is correct
4 Correct 88 ms 2964 KB Output is correct
5 Correct 82 ms 3148 KB Output is correct
6 Correct 86 ms 3076 KB Output is correct
7 Correct 83 ms 3052 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 213 ms 39348 KB Output is correct
12 Correct 194 ms 40764 KB Output is correct
13 Correct 223 ms 39472 KB Output is correct
14 Correct 221 ms 39372 KB Output is correct
15 Correct 195 ms 40784 KB Output is correct
16 Correct 225 ms 41296 KB Output is correct
17 Correct 236 ms 41252 KB Output is correct
18 Correct 224 ms 41424 KB Output is correct
19 Correct 201 ms 40700 KB Output is correct
20 Correct 203 ms 40680 KB Output is correct
21 Correct 220 ms 40652 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 488 ms 42284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 37720 KB Output is correct
2 Correct 106 ms 2992 KB Output is correct
3 Correct 85 ms 2944 KB Output is correct
4 Correct 88 ms 2964 KB Output is correct
5 Correct 82 ms 3148 KB Output is correct
6 Correct 86 ms 3076 KB Output is correct
7 Correct 83 ms 3052 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 213 ms 39348 KB Output is correct
12 Correct 194 ms 40764 KB Output is correct
13 Correct 223 ms 39472 KB Output is correct
14 Correct 221 ms 39372 KB Output is correct
15 Correct 195 ms 40784 KB Output is correct
16 Correct 225 ms 41296 KB Output is correct
17 Correct 236 ms 41252 KB Output is correct
18 Correct 224 ms 41424 KB Output is correct
19 Correct 201 ms 40700 KB Output is correct
20 Correct 203 ms 40680 KB Output is correct
21 Correct 220 ms 40652 KB Output is correct
22 Incorrect 813 ms 46560 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 41020 KB Time limit exceeded
2 Halted 0 ms 0 KB -