oj.uz

Submission #405337

# Submission time Handle Problem Language Result Execution time Memory
405337 2021-05-16T09:07:13 Z oolimry Progression (NOI20_progression) C++17
57 / 100
 1222 ms 79380 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 = root->query(1,r-1).sum + firstval;
					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 213 ms 78524 KB Output is correct
2 Correct 110 ms 496 KB Output is correct
3 Correct 115 ms 580 KB Output is correct
4 Correct 109 ms 612 KB Output is correct
5 Correct 111 ms 628 KB Output is correct
6 Correct 110 ms 580 KB Output is correct
7 Correct 111 ms 676 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 242 ms 78400 KB Output is correct
12 Correct 214 ms 78344 KB Output is correct
13 Correct 210 ms 78660 KB Output is correct
14 Correct 213 ms 78640 KB Output is correct
15 Correct 209 ms 78624 KB Output is correct
16 Correct 216 ms 78288 KB Output is correct
17 Correct 216 ms 78276 KB Output is correct
18 Correct 211 ms 78376 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 366 ms 78768 KB Output is correct
2 Correct 99 ms 836 KB Output is correct
3 Correct 95 ms 824 KB Output is correct
4 Correct 86 ms 896 KB Output is correct
5 Correct 104 ms 1000 KB Output is correct
6 Correct 96 ms 964 KB Output is correct
7 Correct 101 ms 972 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 414 ms 78532 KB Output is correct
12 Correct 373 ms 78904 KB Output is correct
13 Correct 423 ms 78484 KB Output is correct
14 Correct 421 ms 78640 KB Output is correct
15 Correct 353 ms 78820 KB Output is correct
16 Correct 423 ms 79224 KB Output is correct
17 Correct 435 ms 79380 KB Output is correct
18 Correct 414 ms 79156 KB Output is correct
19 Correct 365 ms 78596 KB Output is correct
20 Correct 356 ms 78588 KB Output is correct
21 Correct 357 ms 78532 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 740 ms 78268 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 366 ms 78768 KB Output is correct
2 Correct 99 ms 836 KB Output is correct
3 Correct 95 ms 824 KB Output is correct
4 Correct 86 ms 896 KB Output is correct
5 Correct 104 ms 1000 KB Output is correct
6 Correct 96 ms 964 KB Output is correct
7 Correct 101 ms 972 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 414 ms 78532 KB Output is correct
12 Correct 373 ms 78904 KB Output is correct
13 Correct 423 ms 78484 KB Output is correct
14 Correct 421 ms 78640 KB Output is correct
15 Correct 353 ms 78820 KB Output is correct
16 Correct 423 ms 79224 KB Output is correct
17 Correct 435 ms 79380 KB Output is correct
18 Correct 414 ms 79156 KB Output is correct
19 Correct 365 ms 78596 KB Output is correct
20 Correct 356 ms 78588 KB Output is correct
21 Correct 357 ms 78532 KB Output is correct
22 Correct 1140 ms 78224 KB Output is correct
23 Correct 146 ms 580 KB Output is correct
24 Correct 145 ms 564 KB Output is correct
25 Correct 154 ms 568 KB Output is correct
26 Correct 149 ms 492 KB Output is correct
27 Correct 153 ms 664 KB Output is correct
28 Correct 174 ms 596 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 1124 ms 78256 KB Output is correct
33 Correct 1040 ms 78252 KB Output is correct
34 Correct 1136 ms 78224 KB Output is correct
35 Correct 1118 ms 78136 KB Output is correct
36 Correct 962 ms 78520 KB Output is correct
37 Correct 981 ms 78388 KB Output is correct
38 Correct 939 ms 78508 KB Output is correct
39 Correct 1066 ms 78224 KB Output is correct
40 Correct 1222 ms 78400 KB Output is correct
41 Correct 1186 ms 78264 KB Output is correct
42 Correct 1157 ms 78336 KB Output is correct
43 Correct 1026 ms 78172 KB Output is correct
44 Correct 1048 ms 78288 KB Output is correct
45 Correct 1047 ms 78240 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 78524 KB Output is correct
2 Correct 110 ms 496 KB Output is correct
3 Correct 115 ms 580 KB Output is correct
4 Correct 109 ms 612 KB Output is correct
5 Correct 111 ms 628 KB Output is correct
6 Correct 110 ms 580 KB Output is correct
7 Correct 111 ms 676 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 242 ms 78400 KB Output is correct
12 Correct 214 ms 78344 KB Output is correct
13 Correct 210 ms 78660 KB Output is correct
14 Correct 213 ms 78640 KB Output is correct
15 Correct 209 ms 78624 KB Output is correct
16 Correct 216 ms 78288 KB Output is correct
17 Correct 216 ms 78276 KB Output is correct
18 Correct 211 ms 78376 KB Output is correct
19 Incorrect 3 ms 460 KB Output isn't correct
20 Halted 0 ms 0 KB -