oj.uz

Submission #602352

# Submission time Handle Problem Language Result Execution time Memory
602352 2022-07-22T23:42:45 Z verngutz Progression (NOI20_progression) C++17
35 / 100
 3000 ms 44160 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; }
vector<ll> a;
struct segtree {
    segtree* l;
    segtree* r;
    int L, R;
    ll delta;
    int longest_suff, longest_pref, longest, longest_start_index;
    segtree(int L, int R): L(L), R(R), delta(0) {
        if(R - L > 1) {
            int M = (L + R) / 2;
            l = new segtree(L, M);
            r = new segtree(M, R);
        } else {
            l = nullptr;
            r = nullptr;
        }
    }
    void combine() {
        int M = (L + R) / 2;
        longest_suff = r->longest_suff;
        if(r->longest_suff == r->len() && l->back() == r->front()) {
            longest_suff += l->longest_suff;
        }
        longest_pref = l->longest_pref;
        if(l->longest_pref == l->len() && l->back() == r->front()) {
            longest_pref += r->longest_pref;
        }
        int crossing = l->back() == r->front() ? 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) {
            longest_start_index = M - l->longest_suff;
        } else {
            longest_start_index = l->longest_start_index;
        }
    }
    void build() {
        delta = 0;
        if(R - L > 1) {
            r->build();
            l->build();
            combine();
        } else {
            longest_suff = 1;
            longest_pref = 1;
            longest = 1;
            longest_start_index = L;
        }
    }
    ll front() {
        if(delta == 0 and l != nullptr) {
            return l->front();
        } else {
            return a[L] + delta;
        }
    }
    ll back() {
        if(delta == 0 and r != nullptr) {
            return r->back();
        } else {
            return a[R - 1] + delta;
        }
    }
    int len() {
        return R - L;
    }
    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 {
            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);
            int crossing = l->back() == r->front() 
                ? min(l->longest_suff, M - s) + min(r->longest_pref, e - M)
                : 0;
            int crossing_start_index = l->back() == r->front() 
                ? 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) {
            delta += x;
        } else if(R <= s or e <= L) {
            return;
        } else {
            if(delta != 0) {
                l->delta += delta;
                r->delta += delta;
                delta = 0;
            }
            l->increment(s, e, x);
            r->increment(s, e, x);
            combine();
        }
    }
    ~segtree() {
        delete l;
        delete r;
    }
    void print() {
        if(R - L > 1) {
            if(delta == 0) {
                l->print();
                r->print();
            } else {
                for(int i = L; i < R; i++) {
                    cerr << a[i] + delta << " ";
                }
            }
        } else {
            cerr << a[L] + delta << " ";
        }
    }
    void debug(int depth = 0) {
        for(int i = 0; i < depth; i++) {
            cerr << "\t";
        }
        err(L, R, delta, longest, longest_pref, longest_suff, back(), front());
        if(R - L > 1) {
            l->debug(depth + 1);
            r->debug(depth + 1);
        }
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> d(n);
    cin >> d;
    a.resize(n);
    adjacent_difference(d.begin(), d.end(), a.begin());
    segtree st(0, n);
    st.build();
    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());
            st.build();
        } 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 3082 ms 42820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 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 1508 ms 43728 KB Output is correct
2 Correct 431 ms 784 KB Output is correct
3 Correct 427 ms 836 KB Output is correct
4 Correct 424 ms 908 KB Output is correct
5 Correct 450 ms 876 KB Output is correct
6 Correct 437 ms 1080 KB Output is correct
7 Correct 430 ms 908 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 2037 ms 43372 KB Output is correct
12 Correct 1512 ms 43836 KB Output is correct
13 Correct 1952 ms 43588 KB Output is correct
14 Correct 1942 ms 43264 KB Output is correct
15 Correct 1488 ms 43568 KB Output is correct
16 Correct 1954 ms 43988 KB Output is correct
17 Correct 1990 ms 44036 KB Output is correct
18 Correct 1956 ms 44160 KB Output is correct
19 Correct 1654 ms 43304 KB Output is correct
20 Correct 1644 ms 43524 KB Output is correct
21 Correct 1699 ms 43404 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 43728 KB Output is correct
2 Correct 431 ms 784 KB Output is correct
3 Correct 427 ms 836 KB Output is correct
4 Correct 424 ms 908 KB Output is correct
5 Correct 450 ms 876 KB Output is correct
6 Correct 437 ms 1080 KB Output is correct
7 Correct 430 ms 908 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 2037 ms 43372 KB Output is correct
12 Correct 1512 ms 43836 KB Output is correct
13 Correct 1952 ms 43588 KB Output is correct
14 Correct 1942 ms 43264 KB Output is correct
15 Correct 1488 ms 43568 KB Output is correct
16 Correct 1954 ms 43988 KB Output is correct
17 Correct 1990 ms 44036 KB Output is correct
18 Correct 1956 ms 44160 KB Output is correct
19 Correct 1654 ms 43304 KB Output is correct
20 Correct 1644 ms 43524 KB Output is correct
21 Correct 1699 ms 43404 KB Output is correct
22 Incorrect 1279 ms 43056 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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