oj.uz

Submission #602356

# Submission time Handle Problem Language Result Execution time Memory
602356 2022-07-23T00:20:23 Z verngutz Progression (NOI20_progression) C++17
48 / 100
 3000 ms 61536 KB 
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
struct segtree {
    segtree* l;
    segtree* r;
    int L, R;
    bool is_lazy;
    ll front, back, delta;
    int longest_suff, longest_pref, longest, longest_start_index;
    segtree(vector<ll>& a, int L, int R): L(L), R(R), is_lazy(false), delta(0) {
        if(R - L > 1) {
            int M = (L + R) / 2;
            l = new segtree(a, L, M);
            r = new segtree(a, M, R);
            combine();
        } else {
            l = nullptr;
            r = nullptr;
            front = back = a[L];
            longest_suff = 1;
            longest_pref = 1;
            longest = 1;
            longest_start_index = L;
        }
    }
    int len() {
        return R - L;
    }
    void combine() {
        front = l->get_front();
        back = r->get_back();
        bool can_cross = l->get_back() == r->get_front();
        longest_suff = r->longest_suff;
        if(r->longest_suff == r->len() && can_cross) {
            longest_suff += l->longest_suff;
        }
        longest_pref = l->longest_pref;
        if(l->longest_pref == l->len() && can_cross) {
            longest_pref += r->longest_pref;
        }
        int crossing = can_cross ? l->longest_suff + r->longest_pref : 0;
        longest = max({l->longest, r->longest, crossing});
        if(longest == r->longest) {
            longest_start_index = r->longest_start_index;
        } else if(longest == crossing) {
            int M = (L + R) / 2;
            longest_start_index = M - l->longest_suff;
        } else {
            longest_start_index = l->longest_start_index;
        }
    }
    void lazy(ll x) {
        is_lazy = true;
        delta += x;
    }
    void unlazy() {
        if(is_lazy) {
            if(len() > 1) {
                l->lazy(delta);
                r->lazy(delta);    
            }
            is_lazy = false;
            delta = 0;
            combine();
        }
    }
    ll get_front() {
        return is_lazy ? front + delta : front;
    }
    ll get_back() {
        return is_lazy ? back + delta : back;
    }
    pair<int, int> query(int s, int e) {
        if(s <= L and R <= e) {
            return {longest, longest_start_index};
        } else if(R <= s or e <= L) {
            return {0, -1};
        } else {
            unlazy();
            int M = (L + R) / 2;
            auto [L_longest, L_start_index] = l->query(s, e);
            auto [R_longest, R_start_index] = r->query(s, e);
            bool can_cross = l->get_back() == r->get_front() ;
            int crossing = can_cross ? min(l->longest_suff, M - s) + min(r->longest_pref, e - M) : 0;
            int crossing_start_index = can_cross ? max(M - l->longest_suff, s) : -1;
            int ans = max({L_longest, R_longest, crossing});
            int index;
            if(ans == R_longest) {
                index = R_start_index;
            } else if(ans == crossing) {
                index = crossing_start_index;
            } else {
                index = max(L_start_index, s);
            }
            return {ans, index};
        }
    }
    void increment(int s, int e, ll x) {
        if(s <= L and R <= e) {
            lazy(x);
        } else if(R <= s or e <= L) {
            return;
        } else {
            unlazy();
            l->increment(s, e, x);
            r->increment(s, e, x);
            combine();
        }
    }
    ~segtree() {
        delete l;
        delete r;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> d(n), a(n);
    cin >> d;
    adjacent_difference(d.begin(), d.end(), a.begin());
    segtree st(a, 0, n);
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int L, R, S, C;
            cin >> L >> R >> S >> C;
            L--, R--;
            st.increment(L, L + 1, S);
            if(R + 1 < n) {
                st.increment(R + 1, R + 2, -S);
            }
            st.increment(L + 1, R + 1, C);
            if(R + 1 < n) {
                st.increment(R + 1, R + 2, ll(R - L) * -C);
            }
        } else if(t == 2) {
            int L, R, S, C;
            cin >> L >> R >> S >> C;
            L--, R--;
            for(int i = L; i <= R; i++) {
                d[i] = S + ll(i - L) * C;
            }
            adjacent_difference(d.begin(), d.end(), a.begin());
        } else {
            int L, R;
            cin >> L >> R;
            L--, R--;
            auto [longest, longest_start_index] = st.query(L, R + 1);
            cout << longest + (longest_start_index != L) << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 53012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 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 671 ms 52904 KB Output is correct
2 Correct 425 ms 860 KB Output is correct
3 Correct 434 ms 948 KB Output is correct
4 Correct 445 ms 860 KB Output is correct
5 Correct 443 ms 980 KB Output is correct
6 Correct 432 ms 1004 KB Output is correct
7 Correct 435 ms 876 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 757 ms 52720 KB Output is correct
12 Correct 703 ms 53008 KB Output is correct
13 Correct 760 ms 52764 KB Output is correct
14 Correct 805 ms 52940 KB Output is correct
15 Correct 728 ms 53156 KB Output is correct
16 Correct 764 ms 53372 KB Output is correct
17 Correct 755 ms 53368 KB Output is correct
18 Correct 750 ms 53432 KB Output is correct
19 Correct 732 ms 52792 KB Output is correct
20 Correct 781 ms 52680 KB Output is correct
21 Correct 690 ms 52628 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 53284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 52904 KB Output is correct
2 Correct 425 ms 860 KB Output is correct
3 Correct 434 ms 948 KB Output is correct
4 Correct 445 ms 860 KB Output is correct
5 Correct 443 ms 980 KB Output is correct
6 Correct 432 ms 1004 KB Output is correct
7 Correct 435 ms 876 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 757 ms 52720 KB Output is correct
12 Correct 703 ms 53008 KB Output is correct
13 Correct 760 ms 52764 KB Output is correct
14 Correct 805 ms 52940 KB Output is correct
15 Correct 728 ms 53156 KB Output is correct
16 Correct 764 ms 53372 KB Output is correct
17 Correct 755 ms 53368 KB Output is correct
18 Correct 750 ms 53432 KB Output is correct
19 Correct 732 ms 52792 KB Output is correct
20 Correct 781 ms 52680 KB Output is correct
21 Correct 690 ms 52628 KB Output is correct
22 Correct 1158 ms 52580 KB Output is correct
23 Correct 342 ms 3532 KB Output is correct
24 Correct 307 ms 3616 KB Output is correct
25 Correct 316 ms 3544 KB Output is correct
26 Correct 305 ms 3648 KB Output is correct
27 Correct 331 ms 3532 KB Output is correct
28 Correct 329 ms 3528 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1226 ms 58500 KB Output is correct
33 Correct 1099 ms 61224 KB Output is correct
34 Correct 1123 ms 58512 KB Output is correct
35 Correct 1148 ms 58500 KB Output is correct
36 Correct 1086 ms 58428 KB Output is correct
37 Correct 1061 ms 58520 KB Output is correct
38 Correct 1046 ms 58316 KB Output is correct
39 Correct 1141 ms 61340 KB Output is correct
40 Correct 1155 ms 61536 KB Output is correct
41 Correct 1225 ms 61488 KB Output is correct
42 Correct 1180 ms 61388 KB Output is correct
43 Correct 1079 ms 61352 KB Output is correct
44 Correct 1098 ms 61164 KB Output is correct
45 Correct 1064 ms 61368 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 53012 KB Time limit exceeded
2 Halted 0 ms 0 KB -