Submission #1264458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264458		goulthen	Progression (NOI20_progression)	C++20	48 / 100	419 ms	68372 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;
	bool flag=0;
};

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

	void apply(int i, int x) {
		// TODO
	}

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

		v[i].pv += lazy[i];
		v[i].sv += lazy[i];

		if (l!=r) {
			lazy[2*i] += lazy[i];
			lazy[2*i+1] += lazy[i];
		}
		lazy[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);
		return z;
	}

	void build(int i, int l, int r) {
		if (l==r) {
			v[i] = {1,1,1,dif[l],dif[r],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) {
		flush(i,l,r);
		if (r < li || l > ri) return;
		if (l >= li && ri >= r) {
			lazy[i] += x;
			flush(i,l,r);
			return;
		}

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

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

	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};
		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);

	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;
			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);
		}
	}
	return 0;
}

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