Submission #262551

#	Time	Username	Problem	Language	Result	Execution time	Memory
262551		Cantfindme	Progression (NOI20_progression)	C++17	0 / 100	438 ms	72648 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);

const int maxn = 300010;

struct rmqv {
	pi pref, suff, best;
};

struct node {
	int s,m,e;
	int sz;
	pi pref, suff, best; //length, value
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		sz = e - s + 1;
		pref = suff = best = pi(0,0);
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void update(int x, int newv) {
		if (s == e) {
			pref = pi(1,newv);
			suff = pi(1,newv);
			return;
		}
		else if (x <= m) l -> update(x,newv);
		else if (x > m) r -> update(x,newv);
		
		pref = l -> pref;
		if (((l->pref).f == l -> sz) and (l->pref).s == (r->pref).s) {
			pref.f = l -> pref.f + r -> pref.f;
		}
		suff = r -> suff;
		if (r->suff.f == r -> sz and r -> suff.s == l->suff.s) {
			suff.f = r->suff.f + l->suff.f;
		}
		
		best = max(l -> best, r -> best);
		best = max(best, pi(min(l -> suff.f, l->sz-1), l -> suff.s));
		best = max(best, r -> pref);
		
		if (l -> suff.s == r -> pref.s) {
			pi combine = pi(min(l -> suff.f, l->sz-1) + min(r->pref.f, r->sz-1), r->pref.s);
			best = max(best,combine);
		}
	}
	
	void debug() {
		cout << s << " " << e << "\n";
		cout << "PREF: " << pref.f << " " << pref.s << "\n";
		cout << "SUFF: " << suff.f << " " << suff.s << "\n";
		cout << "BEST: " << best.f << " " << best.s << "\n";
		if (s != e) {
			l -> debug();
			r -> debug();
		}
	}
	
	rmqv rmq(int x, int y) {
		//cout << "Q: " << s << " " << e << " " << x << " " << y << "\n";
		if (s == x and e == y) return {pref,suff,best};
		else if (x > m) return r -> rmq(x,y);
		else if (y <= m) return l -> rmq(x,y);
		else {
			rmqv left = l -> rmq(x,m);
			rmqv right = r -> rmq(m+1,y);
			int szleft = m - x + 1, szright = y - m + 1 + 1;
			
			pi npref = left.pref;
			pi nsuff = right.suff;
			pi nbest = max(left.best,right.best);
			
			if (left.pref.s == right.pref.s and left.pref.f == szleft) {
				npref = pi(left.pref.f + right.pref.f, left.pref.s);
			}
			
			if (right.suff.s == left.suff.s and right.suff.f == szright) {
				nsuff = pi(right.suff.f + left.suff.f, right.pref.s);
			}
			
			nbest = max(nbest, pi(min(left.suff.f, szleft-1), left.suff.s));
			nbest = max(nbest, right.pref);
			if (left.suff.s == right.pref.s) {
				pi combine = pi(min(left.suff.f, szleft-1) + min(right.pref.f, szright-1), right.pref.s);
				nbest = max(nbest,combine);
			}
			
			return {npref,nsuff,nbest};
		}
	}
	
} *root;

int n,Q;
int A[maxn];
int D[maxn];

int32_t main() {
	FAST
	cin >> n >> Q;
	for (int i =1;i<=n;i++) cin >> A[i];
	for (int i =1;i<=n;i++) D[i] = A[i] - A[i-1];

	root = new node(1,n);
	for (int i =1;i<=n;i++) {
		//cout << i << " " << D[i] << "\n";
		root -> update(i,D[i]);
	}
	
	//root -> debug();
	
	for (int q = 0; q < Q; q++) {
		int type; cin >> type;
		if (type == 1) {
			continue;
		} else if (type == 2) {
			continue;
		} else if (type == 3) {
			int x,y; cin >> x >> y;
			rmqv ans = root -> rmq(x,y);
			int rans = max(ans.pref.f, min(y - x + 1, ans.suff.f + 1));
			rans = max(rans, min(y-x+1,ans.best.f + 1));
			
			cout << rans << "\n";
		}
	}


}

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