oj.uz

Submission #405324

# Submission time Handle Problem Language Result Execution time Memory
405324 2021-05-16T08:55:37 Z oolimry Progression (NOI20_progression) C++17
57 / 100
 1273 ms 79344 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){
			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 223 ms 78400 KB Output is correct
2 Correct 121 ms 508 KB Output is correct
3 Correct 119 ms 556 KB Output is correct
4 Correct 134 ms 528 KB Output is correct
5 Correct 119 ms 636 KB Output is correct
6 Correct 112 ms 580 KB Output is correct
7 Correct 130 ms 532 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 221 ms 78400 KB Output is correct
12 Correct 222 ms 78324 KB Output is correct
13 Correct 220 ms 78632 KB Output is correct
14 Correct 220 ms 78584 KB Output is correct
15 Correct 216 ms 78588 KB Output is correct
16 Correct 241 ms 78304 KB Output is correct
17 Correct 226 ms 78404 KB Output is correct
18 Correct 235 ms 78272 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 378 ms 78916 KB Output is correct
2 Correct 98 ms 832 KB Output is correct
3 Correct 94 ms 896 KB Output is correct
4 Correct 89 ms 964 KB Output is correct
5 Correct 96 ms 948 KB Output is correct
6 Correct 97 ms 968 KB Output is correct
7 Correct 98 ms 964 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 424 ms 78588 KB Output is correct
12 Correct 355 ms 78916 KB Output is correct
13 Correct 436 ms 78488 KB Output is correct
14 Correct 410 ms 78580 KB Output is correct
15 Correct 355 ms 78756 KB Output is correct
16 Correct 423 ms 79156 KB Output is correct
17 Correct 428 ms 79172 KB Output is correct
18 Correct 445 ms 79344 KB Output is correct
19 Correct 357 ms 78472 KB Output is correct
20 Correct 362 ms 78404 KB Output is correct
21 Correct 356 ms 78548 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 78152 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 78916 KB Output is correct
2 Correct 98 ms 832 KB Output is correct
3 Correct 94 ms 896 KB Output is correct
4 Correct 89 ms 964 KB Output is correct
5 Correct 96 ms 948 KB Output is correct
6 Correct 97 ms 968 KB Output is correct
7 Correct 98 ms 964 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 424 ms 78588 KB Output is correct
12 Correct 355 ms 78916 KB Output is correct
13 Correct 436 ms 78488 KB Output is correct
14 Correct 410 ms 78580 KB Output is correct
15 Correct 355 ms 78756 KB Output is correct
16 Correct 423 ms 79156 KB Output is correct
17 Correct 428 ms 79172 KB Output is correct
18 Correct 445 ms 79344 KB Output is correct
19 Correct 357 ms 78472 KB Output is correct
20 Correct 362 ms 78404 KB Output is correct
21 Correct 356 ms 78548 KB Output is correct
22 Correct 1149 ms 78180 KB Output is correct
23 Correct 148 ms 596 KB Output is correct
24 Correct 143 ms 496 KB Output is correct
25 Correct 145 ms 580 KB Output is correct
26 Correct 153 ms 488 KB Output is correct
27 Correct 154 ms 588 KB Output is correct
28 Correct 148 ms 580 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 1193 ms 78304 KB Output is correct
33 Correct 1059 ms 78256 KB Output is correct
34 Correct 1148 ms 78224 KB Output is correct
35 Correct 1150 ms 78312 KB Output is correct
36 Correct 966 ms 78388 KB Output is correct
37 Correct 932 ms 78404 KB Output is correct
38 Correct 989 ms 78352 KB Output is correct
39 Correct 1127 ms 78184 KB Output is correct
40 Correct 1239 ms 78236 KB Output is correct
41 Correct 1273 ms 78236 KB Output is correct
42 Correct 1247 ms 78156 KB Output is correct
43 Correct 1126 ms 78096 KB Output is correct
44 Correct 1122 ms 78096 KB Output is correct
45 Correct 1088 ms 78144 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 78400 KB Output is correct
2 Correct 121 ms 508 KB Output is correct
3 Correct 119 ms 556 KB Output is correct
4 Correct 134 ms 528 KB Output is correct
5 Correct 119 ms 636 KB Output is correct
6 Correct 112 ms 580 KB Output is correct
7 Correct 130 ms 532 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 221 ms 78400 KB Output is correct
12 Correct 222 ms 78324 KB Output is correct
13 Correct 220 ms 78632 KB Output is correct
14 Correct 220 ms 78584 KB Output is correct
15 Correct 216 ms 78588 KB Output is correct
16 Correct 241 ms 78304 KB Output is correct
17 Correct 226 ms 78404 KB Output is correct
18 Correct 235 ms 78272 KB Output is correct
19 Incorrect 3 ms 460 KB Output isn't correct
20 Halted 0 ms 0 KB -