Submission #602372

#	Time	Username	Problem	Language	Result	Execution time	Memory
602372		verngutz	Progression (NOI20_progression)	C++17	100 / 100	1703 ms	71720 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; }
enum struct lazy { increment, set, none };
struct segtree {
    segtree* l;
    segtree* r;
    int L, R;
    lazy flag;
    ll front, back, delta;
    int longest_suff, longest_pref, longest, longest_start_index;
    ll range_sum;
    segtree(vector<ll>& a, int L, int R): L(L), R(R), flag(lazy::none), 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;
            range_sum = a[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;
        }
        range_sum = l->get_range_sum() + r->get_range_sum();
    }
    void lazy_increment(ll x) {
        if(flag != lazy::set) {
            flag = lazy::increment;
        }
        delta += x;
    }
    void lazy_set(ll x) {
        flag = lazy::set;
        delta = x;
        longest_suff = longest_pref = longest = len();
        longest_start_index = L;
    }
    void unlazy() {
        switch(flag) {
            case lazy::increment:
                l->lazy_increment(delta);
                r->lazy_increment(delta);
                break;
            case lazy::set:
                l->lazy_set(delta);
                r->lazy_set(delta);
                break;
        }
        flag = lazy::none;
        delta = 0;
        combine();
    }
    ll get_front() {
        switch(flag) {
            case lazy::increment:
                return front + delta;
            case lazy::set:
                return delta;
            case lazy::none:
                return front;
        }
    }
    ll get_back() {
        switch(flag) {
            case lazy::increment:
                return back + delta;
            case lazy::set:
                return delta;
            case lazy::none:
                return back;
        }
    }
    ll get_range_sum() {
        switch(flag) {
            case lazy::increment:
                return range_sum + delta * len();
            case lazy::set:
                return delta * len();
            case lazy::none:
                return range_sum;
        }
    }
    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_increment(x);
        } else if(R <= s or e <= L) {
            return;
        } else {
            unlazy();
            l->increment(s, e, x);
            r->increment(s, e, x);
            combine();
        }
    }
    void increment(int i, ll x) {
        increment(i, i + 1, x);
    }
    void set(int s, int e, ll x) {
        if(s <= L and R <= e) {
            lazy_set(x);
        } else if(R <= s or e <= L) {
            return;
        } else {
            unlazy();
            l->set(s, e, x);
            r->set(s, e, x);
            combine();
        }
    }
    void set(int i, ll x) {
        set(i, i + 1, x);
    }
    ll sum(int s, int e) {
        if(s <= L and R <= e) {
            return get_range_sum();
        } else if(R <= s or e <= L) {
            return 0;
        } else {
            unlazy();
            return l->sum(s, e) + r->sum(s, e);
        }
    }
    ll sum(int i) {
        return sum(0, i + 1);
    }
    ~segtree() {
        delete l;
        delete r;
    }
};
void debug(segtree& st, int n) {
    for(int i = 0; i < n; i++) {
        cerr << st.sum(i) << " ";
    }
    cerr << endl;
}
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, S);
            st.increment(R + 1, -S);
            st.increment(L + 1, R + 1, C);
            st.increment(R + 1, ll(R - L) * -C);
        } else if(t == 2) {
            int L, R, S, C;
            cin >> L >> R >> S >> C;
            L--, R--;
            ll orig_after = st.sum(R + 1);
            st.set(L, S - st.sum(L - 1));
            st.set(L + 1, R + 1, C);
            st.set(R + 1, orig_after - st.sum(R));
        } 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;
}

Compilation message (stderr)

Progression.cpp: In member function 'void segtree::unlazy()':
Progression.cpp:78:15: warning: enumeration value 'none' not handled in switch [-Wswitch]
   78 |         switch(flag) {
      |               ^
Progression.cpp: In member function 'll segtree::get_range_sum()':
Progression.cpp:121:5: warning: control reaches end of non-void function [-Wreturn-type]
  121 |     }
      |     ^
Progression.cpp: In member function 'll segtree::get_back()':
Progression.cpp:111:5: warning: control reaches end of non-void function [-Wreturn-type]
  111 |     }
      |     ^
Progression.cpp: In member function 'll segtree::get_front()':
Progression.cpp:101:5: warning: control reaches end of non-void function [-Wreturn-type]
  101 |     }
      |     ^

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17