Submission #405361

#	Time	Username	Problem	Language	Result	Execution time	Memory
405361		oolimry	Progression (NOI20_progression)	C++17	100 / 100	1572 ms	88232 KiB

Progression

#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;
			add = 0;
			rewrite = W;
		}
	}
	
	void push(){
		if(rewrite != inf and s != e){
			l->applyrewrite(rewrite);
			r->applyrewrite(rewrite);
			rewrite = inf;
		}
		if(add != 0 and s != e){
			l->applyadd(add);
			r->applyadd(add);
			add = 0;
		}
	}
	
	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(r != n){
					lint nxtval = firstval;
					nxtval += root->query(1,r).sum;
					//show2(firstval,nxtval);
					root->updaterewrite(r,r,nxtval-((r-l)*b+a));
				}
				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(l != r) root->updaterewrite(l,r-1,b);
				
				if(l == 1) firstval = a;
			}
		}
		
		//for(int i = 1;i <= n-1;i++) cout << root->query(i,i).leftval << " "; cout << '\n';
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17