#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() {
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";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
655 ms |
75260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1618 ms |
78032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
671 ms |
75448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1618 ms |
78032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
655 ms |
75260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
