oj.uz

Submission #405342

# Submission time Handle Problem Language Result Execution time Memory
405342 2021-05-16T09:15:17 Z oolimry Progression (NOI20_progression) C++17
57 / 100
 1146 ms 79300 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, sum;
};

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

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, L.sum+R.sum};
	}
	
	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;
	res.sum = L.sum + R.sum;
	
	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 inf = 1234567890123456;
lint arr[300005];
struct node{
	lint s, e, m;
	thing val;
	lint add = 0;
	lint rewrite = inf;
	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; rewrite = inf;
		}	
	}
	
	void applyadd(lint A){
		val.leftval += A;
		val.rightval += A;
		val.sum += (e-s+1)*A;
		add += A;
	}
	
	void applyrewrite(lint W){
		if(W < inf / 100){
			val.leftval = W;
			val.rightval = W;
			val.leftcnt = (e-s+1);
			val.rightcnt = (e-s+1);
			val.best = (e-s+1);
			val.full = 1;
			val.sum = (e-s+1)*W;
			rewrite = W;
		}
	}
	
	void push(){
		if(add != 0 and s != e){
			l->applyadd(add);
			r->applyadd(add);
			add = 0;
		}
		if(rewrite != inf and s != e){
			l->applyrewrite(rewrite);
			r->applyrewrite(rewrite);
			rewrite = inf;
		}
	}
	
	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);
		}
	}
	
	void updaterewrite(int S, int E, lint W){
		push();
		if(s == S and E == e){
			applyrewrite(W);
			push();
		}
		else{
			if(E <= m) l->updaterewrite(S,E,W);
			else if(S >= m+1) r->updaterewrite(S,E,W);
			else l->updaterewrite(S,m,W), r->updaterewrite(m+1,E,W);
			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;
	lint firstval = 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));
				
				if(l == 1) firstval += a;
			}
			else{
				if(l != r) root->updaterewrite(l,r-1,b);
				if(l != 1){
					lint preval = firstval;
					if(l != 2) preval += root->query(1,l-2).sum;
					//show2(preval, firstval);
					root->updaterewrite(l-1,l-1,a-preval);
				}
				if(r != n){
					lint nxtval = firstval;
					nxtval += root->query(1,r).sum;
					root->updaterewrite(r,r,nxtval-(r-l)*b+a);
				}
				
				if(l == 1) firstval = a;
			}
		}
		
		//for(int i = 1;i <= n-1;i++) cout << root->query(i,i).leftval << " "; cout << '\n';
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 78400 KB Output is correct
2 Correct 108 ms 488 KB Output is correct
3 Correct 109 ms 532 KB Output is correct
4 Correct 109 ms 492 KB Output is correct
5 Correct 111 ms 628 KB Output is correct
6 Correct 109 ms 580 KB Output is correct
7 Correct 116 ms 600 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 213 ms 78332 KB Output is correct
12 Correct 218 ms 78304 KB Output is correct
13 Correct 210 ms 78660 KB Output is correct
14 Correct 218 ms 78588 KB Output is correct
15 Correct 213 ms 78648 KB Output is correct
16 Correct 212 ms 78300 KB Output is correct
17 Correct 220 ms 78276 KB Output is correct
18 Correct 214 ms 78268 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 368 ms 78812 KB Output is correct
2 Correct 101 ms 836 KB Output is correct
3 Correct 94 ms 892 KB Output is correct
4 Correct 84 ms 824 KB Output is correct
5 Correct 97 ms 916 KB Output is correct
6 Correct 96 ms 872 KB Output is correct
7 Correct 96 ms 856 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 78552 KB Output is correct
12 Correct 350 ms 78788 KB Output is correct
13 Correct 432 ms 78660 KB Output is correct
14 Correct 422 ms 78532 KB Output is correct
15 Correct 363 ms 78788 KB Output is correct
16 Correct 426 ms 79172 KB Output is correct
17 Correct 417 ms 79076 KB Output is correct
18 Correct 426 ms 79300 KB Output is correct
19 Correct 372 ms 78532 KB Output is correct
20 Correct 355 ms 78380 KB Output is correct
21 Correct 357 ms 78404 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 740 ms 78184 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 368 ms 78812 KB Output is correct
2 Correct 101 ms 836 KB Output is correct
3 Correct 94 ms 892 KB Output is correct
4 Correct 84 ms 824 KB Output is correct
5 Correct 97 ms 916 KB Output is correct
6 Correct 96 ms 872 KB Output is correct
7 Correct 96 ms 856 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 78552 KB Output is correct
12 Correct 350 ms 78788 KB Output is correct
13 Correct 432 ms 78660 KB Output is correct
14 Correct 422 ms 78532 KB Output is correct
15 Correct 363 ms 78788 KB Output is correct
16 Correct 426 ms 79172 KB Output is correct
17 Correct 417 ms 79076 KB Output is correct
18 Correct 426 ms 79300 KB Output is correct
19 Correct 372 ms 78532 KB Output is correct
20 Correct 355 ms 78380 KB Output is correct
21 Correct 357 ms 78404 KB Output is correct
22 Correct 1101 ms 78412 KB Output is correct
23 Correct 146 ms 564 KB Output is correct
24 Correct 143 ms 492 KB Output is correct
25 Correct 142 ms 576 KB Output is correct
26 Correct 148 ms 496 KB Output is correct
27 Correct 147 ms 600 KB Output is correct
28 Correct 148 ms 528 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1118 ms 78396 KB Output is correct
33 Correct 1070 ms 78276 KB Output is correct
34 Correct 1119 ms 78148 KB Output is correct
35 Correct 1099 ms 78140 KB Output is correct
36 Correct 954 ms 78436 KB Output is correct
37 Correct 957 ms 78608 KB Output is correct
38 Correct 924 ms 78448 KB Output is correct
39 Correct 1102 ms 78116 KB Output is correct
40 Correct 1146 ms 78336 KB Output is correct
41 Correct 1143 ms 78404 KB Output is correct
42 Correct 1138 ms 78256 KB Output is correct
43 Correct 1069 ms 78280 KB Output is correct
44 Correct 1074 ms 78188 KB Output is correct
45 Correct 1076 ms 78116 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 78400 KB Output is correct
2 Correct 108 ms 488 KB Output is correct
3 Correct 109 ms 532 KB Output is correct
4 Correct 109 ms 492 KB Output is correct
5 Correct 111 ms 628 KB Output is correct
6 Correct 109 ms 580 KB Output is correct
7 Correct 116 ms 600 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 213 ms 78332 KB Output is correct
12 Correct 218 ms 78304 KB Output is correct
13 Correct 210 ms 78660 KB Output is correct
14 Correct 218 ms 78588 KB Output is correct
15 Correct 213 ms 78648 KB Output is correct
16 Correct 212 ms 78300 KB Output is correct
17 Correct 220 ms 78276 KB Output is correct
18 Correct 214 ms 78268 KB Output is correct
19 Incorrect 3 ms 460 KB Output isn't correct
20 Halted 0 ms 0 KB -