oj.uz

Submission #835611

# Submission time Handle Problem Language Result Execution time Memory
835611 2023-08-23T16:38:36 Z Liudas Progression (NOI20_progression) C++17
35 / 100
 844 ms 59780 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,1,1,1,1});
    }
    void add_val(int val, node &a){
        a.l += val;
        a.r += val;
    }
    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});
        return c;
    }
    void add(int head, int L, int R, int id, int val){
        if(R-L == 1){
            add_val(val, tree[head]);
            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);
    }

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 54300 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 752 ms 58940 KB Output is correct
2 Correct 452 ms 2988 KB Output is correct
3 Correct 445 ms 2916 KB Output is correct
4 Correct 508 ms 2956 KB Output is correct
5 Correct 449 ms 3140 KB Output is correct
6 Correct 443 ms 3028 KB Output is correct
7 Correct 494 ms 3020 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 789 ms 57512 KB Output is correct
12 Correct 743 ms 58960 KB Output is correct
13 Correct 784 ms 57656 KB Output is correct
14 Correct 844 ms 57504 KB Output is correct
15 Correct 796 ms 58836 KB Output is correct
16 Correct 808 ms 59780 KB Output is correct
17 Correct 813 ms 59464 KB Output is correct
18 Correct 792 ms 59536 KB Output is correct
19 Correct 789 ms 58924 KB Output is correct
20 Correct 761 ms 58784 KB Output is correct
21 Correct 767 ms 58908 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 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 752 ms 58940 KB Output is correct
2 Correct 452 ms 2988 KB Output is correct
3 Correct 445 ms 2916 KB Output is correct
4 Correct 508 ms 2956 KB Output is correct
5 Correct 449 ms 3140 KB Output is correct
6 Correct 443 ms 3028 KB Output is correct
7 Correct 494 ms 3020 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 789 ms 57512 KB Output is correct
12 Correct 743 ms 58960 KB Output is correct
13 Correct 784 ms 57656 KB Output is correct
14 Correct 844 ms 57504 KB Output is correct
15 Correct 796 ms 58836 KB Output is correct
16 Correct 808 ms 59780 KB Output is correct
17 Correct 813 ms 59464 KB Output is correct
18 Correct 792 ms 59536 KB Output is correct
19 Correct 789 ms 58924 KB Output is correct
20 Correct 761 ms 58784 KB Output is correct
21 Correct 767 ms 58908 KB Output is correct
22 Incorrect 237 ms 54308 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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