oj.uz

답안 #405316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405316 2021-05-16T08:43:59 Z oolimry Progression (NOI20_progression) C++17
57 / 100
 1345 ms 86804 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);
				}
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 78404 KB Output is correct
2 Correct 112 ms 3524 KB Output is correct
3 Correct 113 ms 3524 KB Output is correct
4 Correct 111 ms 3520 KB Output is correct
5 Correct 115 ms 3604 KB Output is correct
6 Correct 112 ms 3564 KB Output is correct
7 Correct 110 ms 3524 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 220 ms 86404 KB Output is correct
12 Correct 229 ms 86248 KB Output is correct
13 Correct 220 ms 86664 KB Output is correct
14 Correct 220 ms 86804 KB Output is correct
15 Correct 216 ms 86664 KB Output is correct
16 Correct 220 ms 86340 KB Output is correct
17 Correct 217 ms 86332 KB Output is correct
18 Correct 219 ms 86340 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 78808 KB Output is correct
2 Correct 109 ms 836 KB Output is correct
3 Correct 99 ms 1064 KB Output is correct
4 Correct 86 ms 796 KB Output is correct
5 Correct 95 ms 904 KB Output is correct
6 Correct 98 ms 964 KB Output is correct
7 Correct 99 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 420 ms 78484 KB Output is correct
12 Correct 352 ms 79044 KB Output is correct
13 Correct 422 ms 78836 KB Output is correct
14 Correct 404 ms 78500 KB Output is correct
15 Correct 353 ms 78908 KB Output is correct
16 Correct 450 ms 79116 KB Output is correct
17 Correct 420 ms 79176 KB Output is correct
18 Correct 419 ms 79352 KB Output is correct
19 Correct 349 ms 78472 KB Output is correct
20 Correct 367 ms 78464 KB Output is correct
21 Correct 360 ms 78400 KB Output is correct

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 704 ms 78044 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

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 78808 KB Output is correct
2 Correct 109 ms 836 KB Output is correct
3 Correct 99 ms 1064 KB Output is correct
4 Correct 86 ms 796 KB Output is correct
5 Correct 95 ms 904 KB Output is correct
6 Correct 98 ms 964 KB Output is correct
7 Correct 99 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 420 ms 78484 KB Output is correct
12 Correct 352 ms 79044 KB Output is correct
13 Correct 422 ms 78836 KB Output is correct
14 Correct 404 ms 78500 KB Output is correct
15 Correct 353 ms 78908 KB Output is correct
16 Correct 450 ms 79116 KB Output is correct
17 Correct 420 ms 79176 KB Output is correct
18 Correct 419 ms 79352 KB Output is correct
19 Correct 349 ms 78472 KB Output is correct
20 Correct 367 ms 78464 KB Output is correct
21 Correct 360 ms 78400 KB Output is correct
22 Correct 1240 ms 78288 KB Output is correct
23 Correct 146 ms 580 KB Output is correct
24 Correct 142 ms 496 KB Output is correct
25 Correct 171 ms 580 KB Output is correct
26 Correct 148 ms 604 KB Output is correct
27 Correct 153 ms 580 KB Output is correct
28 Correct 180 ms 604 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1240 ms 78556 KB Output is correct
33 Correct 1177 ms 78316 KB Output is correct
34 Correct 1345 ms 78232 KB Output is correct
35 Correct 1240 ms 78304 KB Output is correct
36 Correct 1065 ms 78600 KB Output is correct
37 Correct 1052 ms 78656 KB Output is correct
38 Correct 1058 ms 78616 KB Output is correct
39 Correct 1213 ms 78204 KB Output is correct
40 Correct 1255 ms 78308 KB Output is correct
41 Correct 1291 ms 78548 KB Output is correct
42 Correct 1272 ms 78380 KB Output is correct
43 Correct 1130 ms 78124 KB Output is correct
44 Correct 1124 ms 78140 KB Output is correct
45 Correct 1247 ms 78176 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 78404 KB Output is correct
2 Correct 112 ms 3524 KB Output is correct
3 Correct 113 ms 3524 KB Output is correct
4 Correct 111 ms 3520 KB Output is correct
5 Correct 115 ms 3604 KB Output is correct
6 Correct 112 ms 3564 KB Output is correct
7 Correct 110 ms 3524 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 220 ms 86404 KB Output is correct
12 Correct 229 ms 86248 KB Output is correct
13 Correct 220 ms 86664 KB Output is correct
14 Correct 220 ms 86804 KB Output is correct
15 Correct 216 ms 86664 KB Output is correct
16 Correct 220 ms 86340 KB Output is correct
17 Correct 217 ms 86332 KB Output is correct
18 Correct 219 ms 86340 KB Output is correct
19 Incorrect 3 ms 460 KB Output isn't correct
20 Halted 0 ms 0 KB -