Submission #1264473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264473		goulthen	Progression (NOI20_progression)	C++20	57 / 100	581 ms	74516 KiB

Progression

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

//#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back

const int MAXN = 3e5 + 10;
int a[MAXN], dif[MAXN],n;

struct Node {
	int ans, pfx, sfx;
	long long pv, sv, sum;
	bool flag=0;
};

struct Seg3 {
	Node v[4*MAXN];
	long long lazy[4*MAXN];
	int tp[4*MAXN];

	void apply(int i, int l, int r, int x, int k) {
		if (k == 2) {
			tp[i] = 2;
			lazy[i] = x;
		} else {
			if (tp[i] == 0) tp[i] = 1;
			lazy[i] += x;
		}
	}

	void flush(int i, int l, int r) {
		if (tp[i] == 0) return;

		if (tp[i] == 2) {
			v[i].pv = lazy[i];
			v[i].sv = lazy[i];
			v[i].sum = lazy[i];
			v[i].ans = v[i].pfx = v[i].sfx = r-l+1;
			v[i].flag = 1;

			if (l!=r) {
				int mid = (l+r)/2;
				apply(2*i, l, mid, lazy[i], 2);
				apply(2*i+1, mid+1, r, lazy[i], 2);
			}
		} else {
			v[i].pv += lazy[i];
			v[i].sv += lazy[i];
			v[i].sum += lazy[i];

			if (l!=r) {
				int mid = (l+r)/2;
				apply(2*i, l, mid, lazy[i], 1);
				apply(2*i+1, mid+1, r, lazy[i], 1);
			}
		}

		lazy[i] = 0;
		tp[i] = 0;
	}

	Node join(Node x, Node y) {
		if (x.ans == -1) return y;
		if (y.ans == -1) return x;

		Node z;
		z.pv = x.pv;
		z.sv = y.sv;
		if (x.flag && y.flag && x.pv == y.pv) z.flag = 1;
		if (x.flag && x.pv == y.pv) z.pfx = x.pfx+y.pfx;
		else z.pfx = x.pfx;

		if (y.flag && y.sv == x.sv) z.sfx = y.sfx + x.sfx;
		else z.sfx = y.sfx;

		z.ans = max(x.ans, y.ans);
		if (x.sv == y.pv) z.ans = max(z.ans,x.sfx+y.pfx);
		z.sum = x.sum + y.sum;
		return z;
	}

	void build(int i, int l, int r) {
		if (l==r) {
			v[i] = {1,1,1,dif[l],dif[r],dif[l],1};
			return;
		}
		int mid = (l+r)/2;
		build(2*i, l, mid);
		build(2*i+1, mid+1, r);
		v[i] = join(v[2*i],v[2*i+1]);
	}

	void update(int i, int l, int r, int li, int ri, int x, int k = 1) {
		flush(i,l,r);
		if (r < li || l > ri) return;
		if (l >= li && ri >= r) {
			apply(i,l,r,x,k);
			flush(i,l,r);
			return;
		}

		int mid = (l+r)/2;
		update(2*i, l, mid, li, ri, x, k);
		update(2*i + 1, mid + 1,r, li, ri, x,k);
		v[i] = join(v[2*i], v[2*i+1]);
	}

	void update(int l, int r, int x, int k = 1) {
		update(1,1,n,l,r,x, k);
	}

	Node query(int i, int l, int r, int li, int ri) {
		flush(i,l,r);
		if (r < li || l > ri) return {-1,0,0,0,0,0,0};
		if (l >= li && ri >= r) return v[i];
		int mid = (l+r)/2;
		return join(query(2*i, l,mid,li,ri), query(2*i+1, mid +1,r, li, ri));
	}

	Node query(int l, int r) {
		return query(1,1,n,l,r);
	}

	Seg3() {}
	Seg3(int n) {
		build(1,1,n);
	}
};

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int q;cin >> n >> q;
	rep(i,1,n) cin >> a[i];
	rep(i,2,n) dif[i] = a[i] - a[i-1];

	Seg3 seg(n);
	int fs = a[1];

	while (q--) {
		int tp,l,r,s,c;cin >> tp >> l >> r;


		if (tp == 3) {
			if (l==r) cout << "1\n";
			else cout << seg.query(l+1,r).ans +1 << '\n';
		} else if (tp == 1) {
			cin >> s >> c;
			if (fs >= l && fs <= r) fs += s;

			seg.update(l,l,s);
			if (l!=r) seg.update(l+1,r,c);
			if (r < n) seg.update(r+1,r+1,-s-(r-l)*c);

		} else {
			cin >> s >> c;
			if (fs >= l && fs <= r) fs = s;

			int x = 0;
			if (l > 1) x = fs + seg.query(2,l-1).sum;
			seg.update(l,l,s-x,2);
			if (l!=r) seg.update(l+1,r,c,2);
			if (r < n) {
				x = fs + seg.query(2,r+1).sum;
				seg.update(r+1,r+1,x-s-(r-l)*c,2);
			}

			
		}



	}
	return 0;
}

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