oj.uz

Submission #835633

# Submission time Handle Problem Language Result Execution time Memory
835633 2023-08-23T16:56:34 Z Liudas Progression (NOI20_progression) C++17
35 / 100
 1022 ms 61500 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;
    vector<int> propagate;
    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});
        propagate.assign(N*2, 0);
    }
    void add_val(int val, node &a){
        a.l += val;
        a.r += val;
    }
    void prop(int head){
        add_val(propagate[head], tree[head]);
        if(head >= N){propagate[head] = 0; return;}
        propagate[head * 2 + 1] += propagate[head];
        propagate[head * 2 + 2] += propagate[head];
        propagate[head] = 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;
        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 l, int r, int val){
        prop(head);
        if(l <= L && R <= r){
            add_val(val, tree[head]);
            return;
        }
        if(L >= r || R <= l){
            return;
        }
        int mid = (L + R) / 2;
        add(head * 2 + 1, L, mid, l, r, val);
        add(head * 2 + 2, mid, R, l, r, val);
        tree[head] = deal_with(tree[head*2+1], tree[head*2+2]);
    }
    void add(int l, int r, int val){
        add(0, 0, N, l, r, val);
    }
    node get(int head, int L, int R, int l, int r){
        prop(head);
        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, i + 1, 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;
        }
        if(a == 1){
            int b, c, d, e;
            cin >> b >> c >> d >> e;
        }
    }
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 60116 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 897 ms 61124 KB Output is correct
2 Correct 475 ms 812 KB Output is correct
3 Correct 464 ms 868 KB Output is correct
4 Correct 468 ms 764 KB Output is correct
5 Correct 471 ms 976 KB Output is correct
6 Correct 465 ms 928 KB Output is correct
7 Correct 474 ms 956 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1022 ms 60840 KB Output is correct
12 Correct 841 ms 61196 KB Output is correct
13 Correct 937 ms 60852 KB Output is correct
14 Correct 977 ms 60960 KB Output is correct
15 Correct 887 ms 61112 KB Output is correct
16 Correct 905 ms 61432 KB Output is correct
17 Correct 915 ms 61400 KB Output is correct
18 Correct 904 ms 61500 KB Output is correct
19 Correct 864 ms 60832 KB Output is correct
20 Correct 870 ms 60856 KB Output is correct
21 Correct 878 ms 60764 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 61124 KB Output is correct
2 Correct 475 ms 812 KB Output is correct
3 Correct 464 ms 868 KB Output is correct
4 Correct 468 ms 764 KB Output is correct
5 Correct 471 ms 976 KB Output is correct
6 Correct 465 ms 928 KB Output is correct
7 Correct 474 ms 956 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1022 ms 60840 KB Output is correct
12 Correct 841 ms 61196 KB Output is correct
13 Correct 937 ms 60852 KB Output is correct
14 Correct 977 ms 60960 KB Output is correct
15 Correct 887 ms 61112 KB Output is correct
16 Correct 905 ms 61432 KB Output is correct
17 Correct 915 ms 61400 KB Output is correct
18 Correct 904 ms 61500 KB Output is correct
19 Correct 864 ms 60832 KB Output is correct
20 Correct 870 ms 60856 KB Output is correct
21 Correct 878 ms 60764 KB Output is correct
22 Incorrect 196 ms 60120 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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