Submission #1264455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264455		goulthen	Progression (NOI20_progression)	C++20	35 / 100	189 ms	51140 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];

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

	Node query(int i, int l, int r, int li, int ri) {
		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;cin >> tp >> l >> r;
		if (tp == 3) {
			if (l==r) cout << "1\n";
			else cout << seg.query(l+1,r).ans +1 << '\n';
		}
	}
	return 0;
}

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