oj.uz

Submission #405314

# Submission time Handle Problem Language Result Execution time Memory
405314 2021-05-16T08:41:42 Z oolimry Progression (NOI20_progression) C++17
48 / 100
 1354 ms 157804 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};
}

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)*add;
		add += A;
	}
	
	void applyrewrite(lint W){
		if(W != inf){
			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)*add;
			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 = root->query(1, l-1).sum + firstval;
					root->updaterewrite(l-1,l-1,a-preval);
				}
				else{
					lint nxtval = root->query(1,r-1).sum + firstval;
					root->updaterewrite(r,r,nxtval-(r-l)*b+a);
				}
				
				if(l == 1) firstval = a;
			}
		}
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 157804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

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 359 ms 78788 KB Output is correct
2 Correct 99 ms 896 KB Output is correct
3 Correct 99 ms 788 KB Output is correct
4 Correct 94 ms 900 KB Output is correct
5 Correct 98 ms 1028 KB Output is correct
6 Correct 96 ms 976 KB Output is correct
7 Correct 95 ms 912 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 419 ms 78512 KB Output is correct
12 Correct 358 ms 78908 KB Output is correct
13 Correct 451 ms 78568 KB Output is correct
14 Correct 419 ms 78720 KB Output is correct
15 Correct 428 ms 78784 KB Output is correct
16 Correct 419 ms 79108 KB Output is correct
17 Correct 462 ms 79112 KB Output is correct
18 Correct 413 ms 79172 KB Output is correct
19 Correct 419 ms 78404 KB Output is correct
20 Correct 353 ms 78416 KB Output is correct
21 Correct 369 ms 78404 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 726 ms 78068 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 359 ms 78788 KB Output is correct
2 Correct 99 ms 896 KB Output is correct
3 Correct 99 ms 788 KB Output is correct
4 Correct 94 ms 900 KB Output is correct
5 Correct 98 ms 1028 KB Output is correct
6 Correct 96 ms 976 KB Output is correct
7 Correct 95 ms 912 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 419 ms 78512 KB Output is correct
12 Correct 358 ms 78908 KB Output is correct
13 Correct 451 ms 78568 KB Output is correct
14 Correct 419 ms 78720 KB Output is correct
15 Correct 428 ms 78784 KB Output is correct
16 Correct 419 ms 79108 KB Output is correct
17 Correct 462 ms 79112 KB Output is correct
18 Correct 413 ms 79172 KB Output is correct
19 Correct 419 ms 78404 KB Output is correct
20 Correct 353 ms 78416 KB Output is correct
21 Correct 369 ms 78404 KB Output is correct
22 Correct 1297 ms 78408 KB Output is correct
23 Correct 161 ms 616 KB Output is correct
24 Correct 142 ms 480 KB Output is correct
25 Correct 145 ms 552 KB Output is correct
26 Correct 152 ms 580 KB Output is correct
27 Correct 179 ms 528 KB Output is correct
28 Correct 149 ms 488 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 1328 ms 78208 KB Output is correct
33 Correct 1198 ms 78180 KB Output is correct
34 Correct 1270 ms 78448 KB Output is correct
35 Correct 1255 ms 78340 KB Output is correct
36 Correct 1045 ms 78360 KB Output is correct
37 Correct 1061 ms 78508 KB Output is correct
38 Correct 1066 ms 78448 KB Output is correct
39 Correct 1313 ms 78160 KB Output is correct
40 Correct 1354 ms 78252 KB Output is correct
41 Correct 1341 ms 78212 KB Output is correct
42 Correct 1308 ms 78264 KB Output is correct
43 Correct 1198 ms 78276 KB Output is correct
44 Correct 1211 ms 78368 KB Output is correct
45 Correct 1272 ms 78148 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 157804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -