oj.uz

Submission #835697

# Submission time Handle Problem Language Result Execution time Memory
835697 2023-08-23T17:42:09 Z Liudas Progression (NOI20_progression) C++17
35 / 100
 948 ms 69556 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 + 5);
    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){
            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;
            int t = (c-b) * e + d;
            //cout << "ADDS  " << b << " " << c << " " << d << " " << e << endl;
            //cout << t << endl;
            //tree.add(b, b+1, d);
            //tree.add(b+1,c,e);
            //tree.add(c, c+1, -t);
            //cout << tree.get(b, c).l << " " << tree.get(b, c).r << endl;
        }
    }
    return 0;
}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:115:17: warning: unused variable 't' [-Wunused-variable]
  115 |             int t = (c-b) * e + d;
      |                 ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 420 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 852 ms 67128 KB Output is correct
2 Correct 459 ms 2888 KB Output is correct
3 Correct 457 ms 2892 KB Output is correct
4 Correct 463 ms 2888 KB Output is correct
5 Correct 478 ms 3020 KB Output is correct
6 Correct 463 ms 3108 KB Output is correct
7 Correct 456 ms 3044 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 884 ms 65712 KB Output is correct
12 Correct 856 ms 67204 KB Output is correct
13 Correct 884 ms 65804 KB Output is correct
14 Correct 887 ms 65708 KB Output is correct
15 Correct 840 ms 67120 KB Output is correct
16 Correct 924 ms 67792 KB Output is correct
17 Correct 906 ms 67660 KB Output is correct
18 Correct 890 ms 67804 KB Output is correct
19 Correct 887 ms 67036 KB Output is correct
20 Correct 903 ms 67012 KB Output is correct
21 Correct 948 ms 67000 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 67128 KB Output is correct
2 Correct 459 ms 2888 KB Output is correct
3 Correct 457 ms 2892 KB Output is correct
4 Correct 463 ms 2888 KB Output is correct
5 Correct 478 ms 3020 KB Output is correct
6 Correct 463 ms 3108 KB Output is correct
7 Correct 456 ms 3044 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 884 ms 65712 KB Output is correct
12 Correct 856 ms 67204 KB Output is correct
13 Correct 884 ms 65804 KB Output is correct
14 Correct 887 ms 65708 KB Output is correct
15 Correct 840 ms 67120 KB Output is correct
16 Correct 924 ms 67792 KB Output is correct
17 Correct 906 ms 67660 KB Output is correct
18 Correct 890 ms 67804 KB Output is correct
19 Correct 887 ms 67036 KB Output is correct
20 Correct 903 ms 67012 KB Output is correct
21 Correct 948 ms 67000 KB Output is correct
22 Incorrect 802 ms 69556 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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