| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 834434 | Liudas | Progression (NOI20_progression) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class segment_tree{
public:
struct node{
int l, r;
int lmax, rmax, midmax;
};
vector<node> tree;
int N;
segment_tree(int X){
N = 1;
while(N <= X){
N *= 2;
}
tree.assign(N * 2, {INT_MIN,INT_MIN,0,0,0});
}
node deal_with(node a, node b){
node c = {INT_MIN,INT_MIN,0,0,0};
c.l = a.l;
c.r = b.r;
c.lmax = a.lmax;
c.rmax = b.rmax;
if(a.l == b.l){
c.lmax += b.lmax;
}
if(a.r == b.r){
c.rmax += a.rmax;
}
if(a.r==b.l){
c.midmax = max(c.midmax, a.rmax + b.lmax);
}
c.midmax = max({c.midmax, c.lmax, c.rmax, a.midmax, b.midmax});
//cout << "A " << a.lmax << " " << a.midmax << " " << a.rmax << endl;
//cout << "B " << b.lmax << " " << b.midmax << " " << b.rmax << endl;
//cout << "C " << c.lmax << " " << c.midmax << " " << c.rmax << endl;
return c;
}
void add(int head, int L, int R, int id, int val){
if(R-L == 1){
tree[head] = {val, val, 1, 1, 1};
return;
}
int mid = (L + R) / 2;
if(id < mid){
add(head * 2 + 1, L, mid, id, val);
}
else{
add(head * 2 + 2, mid, R, id, val);
}
tree[head] = deal_with(tree[head*2+1], tree[head*2+2]);
}
void add(int id, int val){
add(0, 0, N, id, val);
}
node get(int head, int L, int R, int l, int r){
if(R - L < 1){
return {INT_MIN, INT_MIN, 0, 0, 0};
}
if(l <= L && R <= r){
return tree[head];
}
if(r <= L || R <= l){
return {INT_MIN, INT_MIN, 0, 0, 0};
}
int mid = (L+R)/2;
return deal_with(get(head * 2 + 1, L, mid, l, r), get(head * 2 + 2, mid, R, l, r));
}
node get(int l, int r){
return get(0, 0, N, l, r);
}
};
int main(){
int N, Q;
cin >> N >> Q;
vector<int> arr(N);
segment_tree tree(N);
for(int i = 0; i < N; i ++){
cin >> arr[i];
if(i > 0){
tree.add(i, arr[i]-arr[i-1]);
}
}
while(Q--){
int a;
cin >> a;
if(a != 3){
return 0;
}
if(a == 3){
int b, c;
cin >> b >> c;
cout << tree.get(b, c).midmax + 1 <<endl;
}
}
return 0;
}