oj.uz

Submission #701754

# Submission time Handle Problem Language Result Execution time Memory
701754 2023-02-22T04:12:08 Z shmad Progression (NOI20_progression) C++17
44 / 100
 274 ms 75576 KB 
#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int N = 1e6 + 5, mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const ld eps = 1e-6;

int n, q, a[N], d[N];

vt<array<int, 5>> qr;

struct Data {
 	int lst, frst, pref, suf, ans, len;
	Data operator + (Data other) const {
		Data res;
		res.len = len + other.len, res.ans = max(ans, other.ans);
		res.frst = frst, res.lst = other.lst;
		res.pref = pref, res.suf = other.suf;
		res.ans = max(ans, other.ans);
		if (lst == other.frst) {
			if (pref == len) res.pref += other.pref;
			if (other.suf == other.len) res.suf += suf;
			res.ans = max(res.ans, suf + other.pref);
		}
		return res;
	}
}t[4 * N];

void build (int v = 1, int tl = 1, int tr = n + 1) {
	if (tl == tr) {
		t[v] = {d[tl], d[tl], 1, 1, 1, 1};
		return;
	}
	int tm = tl + tr >> 1;
	build(v << 1, tl, tm), build(v << 1 | 1, tm + 1, tr);
	t[v] = t[v << 1] + t[v << 1 | 1];
}

void upd (int pos, int x, int v = 1, int tl = 1, int tr = n + 1) {
	if (tl == tr) {
		t[v] = {t[v].frst + x, t[v].lst + x, 1, 1, 1, 1};
		return;
	}
	int tm = tl + tr >> 1;
	if (pos <= tm) upd(pos, x, v << 1, tl, tm);
	else upd(pos, x, v << 1 | 1, tm + 1, tr);
	t[v] = t[v << 1] + t[v << 1 | 1];
}

Data get (int l, int r, int v = 1, int tl = 1, int tr = n + 1) {
	if (tl > r || tr < l) return {0, 0, 0, 0, 0, 0};
	if (tl >= l && tr <= r) return t[v];
	int tm = tl + tr >> 1;
	return get(l, r, v << 1, tl, tm) + get(l, r, v << 1 | 1, tm + 1, tr);
}

void solve () {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
	bool sub1 = 1;
	for (int i = 1; i <= q; i++) {
		int tp, l, r, s = -1, c = -1;
		cin >> tp >> l >> r;
		if (tp < 3) cin >> s >> c;
		qr.pb({tp, l, r, s, c});
	    sub1 &= (l == 1 && r == n);
	}
	if (sub1) {
		int ans = 1, cur = 1, k = a[2] - a[1];
	    for (int i = 1; i < n; i++) {
			if (a[i + 1] - a[i] == k) cur++;
			else {                  	
				k = a[i + 1] - a[i];
				ans = max(ans, cur);
				cur = 2;
			}
	    }
	    ans = max(ans, cur);
		for (auto [tp, l, r, s, c]: qr) {
        	if (tp == 2) ans = n;
        	if (tp == 3) cout << ans << '\n'; 
        }
        return;
	}
	if (max(n, q) <= 0) {
		for (auto [tp, l, r, s, c]: qr) {
		    if (tp == 1) {
		    	for (int i = l; i <= r; i++) a[i] += (s + (i - l) * c);
		    }
		    if (tp == 2) {
				for (int i = l; i <= r; i++) a[i] = (s + (i - l) * c);
		    }
		    if (tp == 3) {
		    	if (l == r) {
		    		cout << "1\n";
		    		continue;
		    	}
		        int ans = 1, cur = 1, k = a[l + 1] - a[l];
		     	for (int i = l; i < r; i++) {
					if (a[i + 1] - a[i] == k) cur++;
					else {
						k = a[i + 1] - a[i];
						ans = max(ans, cur);
						cur = 2;
					}
		     	}
		     	ans = max(ans, cur);
		     	cout << ans << '\n';
		    }
		}
		return;
	}
	build();
	for (auto [tp, l, r, s, c]: qr) {
		if (tp == 3) cout << get(l, r - 1).ans + 1 << '\n';
	}
	cout << '\n';
}

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Compilation message

Progression.cpp: In function 'void build(long long int, long long int, long long int)':
Progression.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
Progression.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
Progression.cpp: In function 'Data get(long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 27196 KB Output is correct
2 Correct 81 ms 21696 KB Output is correct
3 Correct 83 ms 21764 KB Output is correct
4 Correct 83 ms 21584 KB Output is correct
5 Correct 84 ms 21732 KB Output is correct
6 Correct 84 ms 21780 KB Output is correct
7 Correct 81 ms 21760 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 119 ms 26400 KB Output is correct
12 Correct 136 ms 26396 KB Output is correct
13 Correct 120 ms 26436 KB Output is correct
14 Correct 120 ms 26372 KB Output is correct
15 Correct 121 ms 26400 KB Output is correct
16 Correct 123 ms 26356 KB Output is correct
17 Correct 126 ms 26388 KB Output is correct
18 Correct 119 ms 26352 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 67724 KB Output is correct
2 Correct 101 ms 21416 KB Output is correct
3 Correct 95 ms 21408 KB Output is correct
4 Correct 91 ms 21488 KB Output is correct
5 Correct 104 ms 21668 KB Output is correct
6 Correct 97 ms 21456 KB Output is correct
7 Correct 96 ms 21400 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 267 ms 68360 KB Output is correct
12 Correct 245 ms 73244 KB Output is correct
13 Correct 271 ms 71904 KB Output is correct
14 Correct 274 ms 71788 KB Output is correct
15 Correct 242 ms 73136 KB Output is correct
16 Correct 262 ms 73740 KB Output is correct
17 Correct 260 ms 73768 KB Output is correct
18 Correct 268 ms 73780 KB Output is correct
19 Correct 261 ms 73068 KB Output is correct
20 Correct 254 ms 73176 KB Output is correct
21 Correct 240 ms 73176 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 67724 KB Output is correct
2 Correct 101 ms 21416 KB Output is correct
3 Correct 95 ms 21408 KB Output is correct
4 Correct 91 ms 21488 KB Output is correct
5 Correct 104 ms 21668 KB Output is correct
6 Correct 97 ms 21456 KB Output is correct
7 Correct 96 ms 21400 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 267 ms 68360 KB Output is correct
12 Correct 245 ms 73244 KB Output is correct
13 Correct 271 ms 71904 KB Output is correct
14 Correct 274 ms 71788 KB Output is correct
15 Correct 242 ms 73136 KB Output is correct
16 Correct 262 ms 73740 KB Output is correct
17 Correct 260 ms 73768 KB Output is correct
18 Correct 268 ms 73780 KB Output is correct
19 Correct 261 ms 73068 KB Output is correct
20 Correct 254 ms 73176 KB Output is correct
21 Correct 240 ms 73176 KB Output is correct
22 Incorrect 249 ms 75576 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 27196 KB Output is correct
2 Correct 81 ms 21696 KB Output is correct
3 Correct 83 ms 21764 KB Output is correct
4 Correct 83 ms 21584 KB Output is correct
5 Correct 84 ms 21732 KB Output is correct
6 Correct 84 ms 21780 KB Output is correct
7 Correct 81 ms 21760 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 119 ms 26400 KB Output is correct
12 Correct 136 ms 26396 KB Output is correct
13 Correct 120 ms 26436 KB Output is correct
14 Correct 120 ms 26372 KB Output is correct
15 Correct 121 ms 26400 KB Output is correct
16 Correct 123 ms 26356 KB Output is correct
17 Correct 126 ms 26388 KB Output is correct
18 Correct 119 ms 26352 KB Output is correct
19 Incorrect 1 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -