oj.uz

Submission #585048

# Submission time Handle Problem Language Result Execution time Memory
585048 2022-06-28T09:27:33 Z GioChkhaidze Progression (NOI20_progression) C++14
35 / 100
 350 ms 45448 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>

#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r 
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define f first
#define s second

using namespace std;

const int N = 3e5 + 5;

int n, m, q, L, R, S, C, a[N], b[N];

struct node {
	int ans;
	int len;
	int fr;
	int ls;
	int pr;
	int sf;
	int add;
	node () {
		ans = 0;
		len = 0;
		add = 0;
		fr = 0;
		ls = 0;
		pr = 0;
		sf = 0;
	}
};

node v[4 * N], bs;

node mrg(node a, node b) {
	node c;
	c.len = a.len + b.len;
	c.fr = a.fr, c.ls = b.ls;
	c.pr = a.pr, c.sf = b.sf;
	c.ans = max(a.ans, b.ans);
	if (a.ls == b.fr) {
		if (a.len == c.pr) c.pr += b.pr;
		if (b.len == c.sf) c.sf += a.sf;
		c.ans = max(c.ans, a.sf + b.pr);
	}
	return c;
} 

void shift(tree) {
	
}

void build(tree) {
	if (l == r) {
		v[h].pr = v[h].sf = v[h].len = v[h].ans = 1;
		v[h].fr = v[h].ls = b[l];
		return ;
	}
	build(left), build(right);
	v[h] = mrg(v[lf], v[rf]);
}

void up_dot(tree) {
	if (l == r) {

		return;
	}
	shift(h, l, r);
	if (L <= mf) {
		up_dot(left);
	}
		else {
		up_dot(right);
	}
	v[h] = mrg(v[lf], v[rf]);
}

node get(tree) {
	if (r < L || R < l) return bs;
	if (L <= l && r <= R) return v[h];
	shift(h, l, r);
	return mrg(get(left), get(right));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (1 < i) {
			b[i - 1] = a[i] - a[i - 1];
		} 
	}

	m = n + 1;
	build(1, 1, m);
	for (int i = 1; i <= q; ++i) {
		int tp;
		cin >> tp >> L >> R;
		if (tp == 1) {
			cin >> S >> C;
			/*if (L == R) {
				upd_dot(1, 1, n);
			}*/
		}
			else
		if (tp == 2) {
			cin >> S >> C;
			/*if (L == R) {

			}*/
		}
			else
		if (tp == 3) {
			--R; cout << get(1 , 1, m).ans + 1 << "\n";
		}
	}
}

/*
 S + (i − L) × C.

 S + i * C - L * C

 (S - L * C) + i * C

b[i] = a[i + 1] - a[i]



QUERY ADD
QUERY PUT
QUERY 




*/

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 33236 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 288 ms 42644 KB Output is correct
2 Correct 122 ms 35788 KB Output is correct
3 Correct 109 ms 35872 KB Output is correct
4 Correct 107 ms 35788 KB Output is correct
5 Correct 151 ms 36044 KB Output is correct
6 Correct 109 ms 35980 KB Output is correct
7 Correct 103 ms 36008 KB Output is correct
8 Correct 19 ms 33188 KB Output is correct
9 Correct 17 ms 33212 KB Output is correct
10 Correct 20 ms 33212 KB Output is correct
11 Correct 313 ms 41164 KB Output is correct
12 Correct 301 ms 42744 KB Output is correct
13 Correct 340 ms 41312 KB Output is correct
14 Correct 310 ms 41132 KB Output is correct
15 Correct 307 ms 42620 KB Output is correct
16 Correct 297 ms 43188 KB Output is correct
17 Correct 289 ms 43156 KB Output is correct
18 Correct 350 ms 43260 KB Output is correct
19 Correct 259 ms 42584 KB Output is correct
20 Correct 277 ms 42460 KB Output is correct
21 Correct 259 ms 42536 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 42644 KB Output is correct
2 Correct 122 ms 35788 KB Output is correct
3 Correct 109 ms 35872 KB Output is correct
4 Correct 107 ms 35788 KB Output is correct
5 Correct 151 ms 36044 KB Output is correct
6 Correct 109 ms 35980 KB Output is correct
7 Correct 103 ms 36008 KB Output is correct
8 Correct 19 ms 33188 KB Output is correct
9 Correct 17 ms 33212 KB Output is correct
10 Correct 20 ms 33212 KB Output is correct
11 Correct 313 ms 41164 KB Output is correct
12 Correct 301 ms 42744 KB Output is correct
13 Correct 340 ms 41312 KB Output is correct
14 Correct 310 ms 41132 KB Output is correct
15 Correct 307 ms 42620 KB Output is correct
16 Correct 297 ms 43188 KB Output is correct
17 Correct 289 ms 43156 KB Output is correct
18 Correct 350 ms 43260 KB Output is correct
19 Correct 259 ms 42584 KB Output is correct
20 Correct 277 ms 42460 KB Output is correct
21 Correct 259 ms 42536 KB Output is correct
22 Incorrect 261 ms 45028 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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