oj.uz

Submission #834897

# Submission time Handle Problem Language Result Execution time Memory
834897 2023-08-22T23:26:16 Z Liudas Progression (NOI20_progression) C++17
35 / 100
 818 ms 59692 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
#define int long long
using namespace std;
class segment_tree{
public:
    struct node{
        int l, r;
        int lmax, rmax, midmax;
        int siz;
    };
    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,1});
    }
    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;
        c.siz = a.siz + b.siz;
        if(a.r == b.l && a.rmax == a.siz){
            c.lmax += b.lmax;
        }
        if(a.r == b.l && b.lmax == b.siz){
            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 << " " << a.l << " " << a.r << endl;
        //cout << "B " << b.lmax << " " << b.midmax << " " << b.rmax << " " << b.l << " " << b.r << endl;
        //cout << "C " << c.lmax << " " << c.midmax << " " << c.rmax << " " << c.l << " " << c.r << 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, 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);
        }
        //cout << "HEAD  " << head << endl;
        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;
        //cout << head << endl;
        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);
    }

};
signed 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]);
            //cout << arr[i] - arr[i-1] << endl;
        }
    }
    //cout << tree.get(1, 5).midmax + 1 << " " << tree.get(1, 5).lmax << " " << tree.get(1, 5).rmax << endl;
    //cout << tree.get(5, 10).midmax + 1 << " " << tree.get(5, 10).lmax << " " << tree.get(5, 10).rmax << endl;
    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; //<< " " << tree.get(b, c).lmax << " " << tree.get(b, c).rmax << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 54220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 59004 KB Output is correct
2 Correct 458 ms 3060 KB Output is correct
3 Correct 454 ms 2972 KB Output is correct
4 Correct 455 ms 2968 KB Output is correct
5 Correct 458 ms 3408 KB Output is correct
6 Correct 450 ms 3084 KB Output is correct
7 Correct 457 ms 3000 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 304 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 818 ms 57588 KB Output is correct
12 Correct 766 ms 58916 KB Output is correct
13 Correct 790 ms 57484 KB Output is correct
14 Correct 754 ms 57588 KB Output is correct
15 Correct 767 ms 58884 KB Output is correct
16 Correct 802 ms 59648 KB Output is correct
17 Correct 803 ms 59424 KB Output is correct
18 Correct 791 ms 59692 KB Output is correct
19 Correct 775 ms 58816 KB Output is correct
20 Correct 769 ms 58860 KB Output is correct
21 Correct 763 ms 58808 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 54304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 59004 KB Output is correct
2 Correct 458 ms 3060 KB Output is correct
3 Correct 454 ms 2972 KB Output is correct
4 Correct 455 ms 2968 KB Output is correct
5 Correct 458 ms 3408 KB Output is correct
6 Correct 450 ms 3084 KB Output is correct
7 Correct 457 ms 3000 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 304 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 818 ms 57588 KB Output is correct
12 Correct 766 ms 58916 KB Output is correct
13 Correct 790 ms 57484 KB Output is correct
14 Correct 754 ms 57588 KB Output is correct
15 Correct 767 ms 58884 KB Output is correct
16 Correct 802 ms 59648 KB Output is correct
17 Correct 803 ms 59424 KB Output is correct
18 Correct 791 ms 59692 KB Output is correct
19 Correct 775 ms 58816 KB Output is correct
20 Correct 769 ms 58860 KB Output is correct
21 Correct 763 ms 58808 KB Output is correct
22 Incorrect 149 ms 54304 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 54220 KB Output isn't correct
2 Halted 0 ms 0 KB -