Submission #676491

#	Time	Username	Problem	Language	Result	Execution time	Memory
676491		penguin133	Progression (NOI20_progression)	C++17	100 / 100	1270 ms	88264 KiB

Progression

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

int A[300005];


struct pain{
	int val, pmax, smax, pref, suf, len, sm;
};

pain merge(pain l, pain r){
	pain ans;
	ans.val = max(l.val, r.val);
	ans.len = l.len + r.len;
	if(l.suf == r.pref)ans.val = max(ans.val, l.smax + r.pmax);
	ans.suf = r.suf, ans.pref = l.pref;
	ans.pmax = l.pmax, ans.smax = r.smax;
	if(l.suf == r.suf && r.smax == r.len)ans.smax += l.smax;
	if(l.pref == r.pref && l.pmax == l.len)ans.pmax += r.pmax;
	ans.sm = l.sm + r.sm;
	return ans;
}

struct node{
	int s,e,m;
	pain hi;
	bool fix;
	int lazy, lazy2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		lazy = 0;
		fix = 0;
		lazy2 = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			hi = merge(l->hi, r->hi);
		}
		else{
			hi.val = hi.pmax = hi.smax = 1;
			hi.pref = hi.sm = hi.suf = A[s] - A[s-1];
			hi.len = 1;
		}
	}
	void propo(){
		if(fix){
			hi.pmax = hi.smax = hi.val = hi.len, hi.pref = hi.suf = lazy2;
			hi.sm = lazy2 * (e - s + 1);
			fix = 0;
			if(s != e)l->lazy2 = lazy2, r->lazy2 = lazy2, l->fix = 1, r->fix = 1, l->lazy = 0, r->lazy = 0;
		}
		else if(lazy){
			hi.pref += lazy;
			hi.suf += lazy;
			hi.sm += lazy * (e - s + 1);
			if(s != e){
				if(l->fix)l->lazy = 0, l->lazy2 += lazy;
				else l->lazy += lazy;
				if(r->fix)r->lazy = 0, r->lazy2 += lazy;
				else r->lazy += lazy;
			}
		}
		lazy = lazy2 = 0;
	}
	void upd(int a, int b, int c){
		propo();
		if(a == s && b == e){
			if(fix)lazy2 += c;
			else lazy += c;
			propo();
		}
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
			hi = merge(l->hi, r->hi);
		}
	}
	void upd2(int a, int b, int c){
		propo();
		if(a == s && b == e)lazy2 =c, fix = 1, lazy = 0, propo();
		else{
			if(b <= m)l->upd2(a, b, c);
			else if(a > m)r->upd2(a, b, c);
			else l->upd2(a, m, c), r->upd2(m+1, b, c);
			l->propo(), r->propo();
			hi = merge(l->hi ,r->hi);
		}
	}
	pain query(int a, int b){
		propo();
		if(a == s && b == e)return hi;
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return merge(l->query(a, m), r->query(m+1, b));
	}
	void debug(){
		cerr << s << " " << e << " " << hi.val << " " << hi.pref << " " << hi.suf << " " << hi.pmax << " " << hi.smax << " " << hi.len << " " << hi.sm << '\n';
		if(s != e)l->debug(), r->debug();
	}
}*root;


int n,q;
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	root = new node(1, n);
	//root->debug();
	while(q--){
		int x,l,r;cin >> x >> l >> r;
		if(x == 3)cout << (l == r ? 1 : root->query(l+1, r).val + 1) << '\n';
		else if(x == 1){
			int s,c;cin >>s >> c;
			root->upd(l, l, s);
			if(l < r)root->upd(l+1, r, c);
			if(r < n)root->upd(r+1, r+1, -(s + (r-l)*c));
		}
		else{
			int s, c;cin >> s >> c;
			int tmp = 0;
			if(r < n)tmp = root->query(1, r+1).sm;
			if(l > 1){
				//pain test = root->query(1, l-1);
				//cout << test.val << " " << test.pref << " " << test.suf << " " << test.pmax << " " << test.smax << " " << test.len << " " << test.sm << '\n';
				int x = root->query(1, l-1).sm;
				root->upd2(l, l, s-x);
				//cout << s << " " << x << '\n';
			}
			else{
				root->upd2(1, 1, s);
			}
			if(l < r)root->upd2(l+1, r, c);
			if(r < n){
				int x = root->query(1, r).sm;
				root->upd2(r+1, r+1, tmp-(s + (r-l)*c));
			}
		}
	}
}

Compilation message (stderr)

Progression.cpp: In function 'int32_t main()':
Progression.cpp:144:9: warning: unused variable 'x' [-Wunused-variable]
  144 |     int x = root->query(1, r).sm;
      |         ^

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