Submission #601998

#	Time	Username	Problem	Language	Result	Execution time	Memory
601998		verngutz	Progression (NOI20_progression)	C++17	50 / 100	3070 ms	41036 KiB

Progression

#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;
    int longest_eq_suff, longest_eq_pref, longest, longest_start_index;
    segtree(int L, int R): L(L), R(R) {
        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 build() {
        if(R - L > 1) {
            int M = (L + R) / 2;
            r->build();
            l->build();
            longest_eq_suff = r->longest_eq_suff;
            if(r->longest_eq_suff == r->len() && l->back() == r->front()) {
                longest_eq_suff += l->longest_eq_suff;
            }
            longest_eq_pref = l->longest_eq_pref;
            if(l->longest_eq_pref == l->len() && l->back() == r->front()) {
                longest_eq_pref += r->longest_eq_pref;
            }
            int crossing = l->back() == r->front() ? l->longest_eq_suff + r->longest_eq_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_eq_suff;
            } else {
                longest_start_index = l->longest_start_index;
            }
        } else {
            longest_eq_suff = 1;
            longest_eq_pref = 1;
            longest = 1;
            longest_start_index = L;
        }
    }
    int front() {
        return a[L];
    }
    int back() {
        return a[R - 1];
    }
    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_eq_suff, M - s) + min(r->longest_eq_pref, e - M)
                : 0;
            int crossing_start_index = l->back() == r->front() 
                ? max(M - l->longest_eq_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};
        }
    }
    ~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);
    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--;
            for(int i = L; i <= R; i++) {
                d[i] += S + (i - L) * C;
            }
            adjacent_difference(d.begin(), d.end(), a.begin());
            st.build();
        } 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 + (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
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17