oj.uz

Submission #405310

# Submission time Handle Problem Language Result Execution time Memory
405310 2021-05-16T08:15:39 Z oolimry Progression (NOI20_progression) C++17
48 / 100
 1067 ms 68444 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

struct thing{
	lint leftval, rightval, leftcnt, rightcnt, best, full;
};

inline thing single(int u){
	return {u,u,1,1,1,1};
}

inline thing merge(thing L, thing R){
	thing res;
	if(L.full and R.full and L.rightval == R.leftval){
		return {L.leftval, R.rightval, L.leftcnt+R.leftcnt, L.rightcnt+R.rightcnt, L.best+R.best, 1};
	}
	
	res.leftval = L.leftval, res.rightval = R.rightval;
	res.leftcnt = L.leftcnt, res.rightcnt = R.rightcnt;
	res.best = max(L.best, R.best);
	res.full = 0;
	
	if(L.rightval == R.leftval){
		res.best = max(res.best, L.rightcnt + R.leftcnt);
		if(L.full) res.leftcnt += R.leftcnt;
		else if(R.full) res.rightcnt += L.rightcnt;
		res.best = max(res.best, res.leftcnt);
		res.best = max(res.best, res.rightcnt);
	}
	
	return res;
}

lint arr[300005];
struct node{
	int s, e, m;
	thing val;
	lint add = 0;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s == e) val = single(arr[s]);
		else{
			l = new node(s,m);
			r = new node(m+1,e);
			val = merge(l->val, r->val);
			add = 0;
		}	
	}
	
	void applyadd(lint A){
		val.leftval += A;
		val.rightval += A;
		add += A;
	}
	
	void push(){
		if(add != 0 and s != e){
			l->applyadd(add);
			r->applyadd(add);
			add = 0;
		}
	}
	
	thing query(int S, int E){
		push();
		if(s == S and E == e) return val;
		else if(E <= m) return l->query(S,E);
		else if(S >= m+1) return r->query(S,E);
		else return merge(l->query(S,m), r->query(m+1,E));
	} 
	
	void updateadd(int S, int E, lint A){
		push();
		if(s == S and E == e){
			applyadd(A);
			push();
		}
		else{
			if(E <= m) l->updateadd(S,E,A);
			else if(S >= m+1) r->updateadd(S,E,A);
			else l->updateadd(S,m,A), r->updateadd(m+1,E,A);
			val = merge(l->val, r->val);
		}
	}
} *root;


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	lint x; cin >> x;
	for(int i = 2;i <= n;i++){
		lint y; cin >> y;
		arr[i-1] = y-x;
		x = y;
	}
	
	if(n != 1) root = new node(1,n-1);
	
	while(Q--){
		lint t, l, r; cin >> t >> l >> r;
		if(t == 3){
			if(l == r) cout << "1\n";
			else cout << root->query(l,r-1).best+1 << '\n';
		}
		else{
			lint a, b; cin >> a >> b;
			if(n == 1) continue;
			if(t == 1){
				if(l != r) root->updateadd(l,r-1,b);
				if(l != 1) root->updateadd(l-1,l-1,a);
				if(r != n) root->updateadd(r,r,-((r-l)*b+a));
			}
		}
	}
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 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 372 ms 60132 KB Output is correct
2 Correct 94 ms 832 KB Output is correct
3 Correct 92 ms 888 KB Output is correct
4 Correct 87 ms 820 KB Output is correct
5 Correct 110 ms 960 KB Output is correct
6 Correct 115 ms 928 KB Output is correct
7 Correct 93 ms 936 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 428 ms 59900 KB Output is correct
12 Correct 393 ms 60068 KB Output is correct
13 Correct 407 ms 59760 KB Output is correct
14 Correct 405 ms 59732 KB Output is correct
15 Correct 340 ms 59924 KB Output is correct
16 Correct 422 ms 60380 KB Output is correct
17 Correct 395 ms 60280 KB Output is correct
18 Correct 424 ms 60484 KB Output is correct
19 Correct 344 ms 59712 KB Output is correct
20 Correct 423 ms 59640 KB Output is correct
21 Correct 345 ms 59664 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 60132 KB Output is correct
2 Correct 94 ms 832 KB Output is correct
3 Correct 92 ms 888 KB Output is correct
4 Correct 87 ms 820 KB Output is correct
5 Correct 110 ms 960 KB Output is correct
6 Correct 115 ms 928 KB Output is correct
7 Correct 93 ms 936 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 428 ms 59900 KB Output is correct
12 Correct 393 ms 60068 KB Output is correct
13 Correct 407 ms 59760 KB Output is correct
14 Correct 405 ms 59732 KB Output is correct
15 Correct 340 ms 59924 KB Output is correct
16 Correct 422 ms 60380 KB Output is correct
17 Correct 395 ms 60280 KB Output is correct
18 Correct 424 ms 60484 KB Output is correct
19 Correct 344 ms 59712 KB Output is correct
20 Correct 423 ms 59640 KB Output is correct
21 Correct 345 ms 59664 KB Output is correct
22 Correct 1027 ms 59436 KB Output is correct
23 Correct 144 ms 484 KB Output is correct
24 Correct 166 ms 604 KB Output is correct
25 Correct 141 ms 620 KB Output is correct
26 Correct 146 ms 672 KB Output is correct
27 Correct 145 ms 584 KB Output is correct
28 Correct 148 ms 544 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1034 ms 65504 KB Output is correct
33 Correct 1002 ms 68288 KB Output is correct
34 Correct 1006 ms 65504 KB Output is correct
35 Correct 1067 ms 65580 KB Output is correct
36 Correct 913 ms 65348 KB Output is correct
37 Correct 869 ms 65328 KB Output is correct
38 Correct 843 ms 65484 KB Output is correct
39 Correct 986 ms 68328 KB Output is correct
40 Correct 1045 ms 68444 KB Output is correct
41 Correct 1036 ms 68348 KB Output is correct
42 Correct 1060 ms 68284 KB Output is correct
43 Correct 941 ms 68292 KB Output is correct
44 Correct 987 ms 68292 KB Output is correct
45 Correct 1014 ms 68372 KB Output is correct

Subtask #6
0 / 17.0

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