Submission #711825

#	Time	Username	Problem	Language	Result	Execution time	Memory
711825		Thienu	Progression (NOI20_progression)	C++17	68 / 100	1771 ms	117228 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

#define u_map unordered_map
#define u_set unordered_set
#define u_multiset unordered_multiset

using ll = long long;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif


namespace segtree {
    /**
     * Range set
     * Range query: longest sequence of same numbers
    */
    const ll INF = 4'234'567'890'123'456'789;
    
    struct QueryOut {
        int ans;
        ll lnum, rnum;
        int llen, rlen;
        bool same;
        int len;
        QueryOut(int ans, ll lnum, int llen, ll rnum, int rlen, bool same, int len) : ans(ans), lnum(lnum), llen(llen), rnum(rnum), rlen(rlen), same(same), len(len) {}
        QueryOut() {len = 0;}
    };

    QueryOut combine(QueryOut x, QueryOut y) {
        if(x.len == 0) return y;
        if(y.len == 0) return x;
        int new_ans = max({x.ans, y.ans});
        if(x.rnum == y.lnum) new_ans = max(new_ans, x.rlen + y.llen);
        return QueryOut(
            new_ans,
            x.lnum,
            (x.same && x.rnum == y.lnum) ? x.llen + y.llen : x.llen,
            y.rnum,
            (y.same && x.rnum == y.lnum) ? y.rlen + x.rlen : y.rlen,
            x.same && y.same && x.rnum == y.lnum,
            x.len + y.len
        );
    }

    struct Node {
        Node *l, *r;
        int lo, hi;

        ll mset = -INF;
        ll madd = 0;

        QueryOut qout;

        Node(int lo, int hi, vll &v): lo(lo), hi(hi) {
            if(lo + 1 == hi){
                // same = true;
                // lnum = rnum = v[lo];
                // llen = rlen = 1;
                qout = QueryOut(1, v[lo], 1, v[lo], 1, true, 1);
            } else {
                int mid = lo + (hi - lo) / 2;
                l = new Node(lo, mid, v);
                r = new Node(mid, hi, v);
                update();
            }
        }

        void update() {
            qout = combine(l->qout, r->qout);
        }

        void push() {
            if(mset != -INF) {
                l->set(lo, hi, mset);
                r->set(lo, hi, mset);
                mset = -INF;
            } else if(madd) {
                l->add(lo, hi, madd);
                r->add(lo, hi, madd);
                madd = 0;
            }
        }

        void set(int left, int right, ll val) {
            assert(val != -INF);
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                mset = val;
                madd = 0;
                qout = QueryOut(hi - lo, val, hi - lo, val, hi - lo, true, hi - lo);
            } else {
                push();
                l->set(left, right, val);
                r->set(left, right, val);
                update();
            }
        }

        void add(int left, int right, ll val) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                if(mset != -INF) {
                    mset += val;
                } else {
                    madd += val;
                }
                debug("add proc", left, right, lo, hi, val);
                qout = QueryOut(qout.ans, qout.lnum + val, qout.llen, qout.rnum + val, qout.rlen, qout.same, hi - lo);
            } else {
                push();
                l->add(left, right, val);
                r->add(left, right, val);
                update();
            }
        }

        QueryOut query(int left, int right) {
            if(right <= lo || hi <= left) return QueryOut(-1, -1, -1, -1, -1, false, 0); // dummy
            if(left <= lo && hi <= right){
                return qout;
            } else {
                push();
                return combine(l->query(left, right), r->query(left, right));
            }
        }
    };
}

namespace lichao {
    const ll INF = 2'000'000'000'000'000'005;

    struct Line{
        ll m, c;
        Line(ll _m, ll _c) : m(_m), c(_c) {}

        ll eval(ll x){
            return m * x + c;
        }

        bool nonzero() {
            return m != 0 || c != 0;
        }
    };
    Line operator+(Line &a, Line &b) { return Line(a.m + b.m, a.c + b.c); }

    ostream& operator<<(ostream &os, Line x) { return os << "{m=" << x.m << ", c=" << x.c << '}'; }

    struct Node {
        Node *l = 0, *r = 0;
        int lo, hi; // [lo, hi)
        Line line = Line(0, INF);
        Line madd = Line(0, 0);
        bool mwipe = false;

        Node(int lo, int hi): lo(lo), hi(hi) {}

        void push() {
            assert(lo + 1 < hi);
            if(!l) {
                int mid = lo + (hi - lo) / 2;
                l = new Node(lo, mid);
                r = new Node(mid, hi);
            }
            if(madd.nonzero()) {
                l->add_affine(lo, hi, madd);
                r->add_affine(lo, hi, madd);
                madd = Line(0, 0);
            }
            if(mwipe) {
                l->wipe(lo, hi);
                r->wipe(lo, hi);
                mwipe = false;
            }
        }

        // Reset all lines on [left, right).
        void wipe(int left, int right) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                madd = Line(0, 0);
                mwipe = true;
                line = Line(0, INF);
            } else {
                push();
                l->wipe(left, right);
                r->wipe(left, right);
            }
        }

        // Insert new_line on [left, right). O(log^2 n) / O(log n) if left=0, right=n.
        void insert_line(int left, int right, Line new_line) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                bool ldiff = line.eval(lo) <= new_line.eval(lo);
                bool rdiff = line.eval(hi - 1) <= new_line.eval(hi - 1);
                if(ldiff && rdiff) return;
                if(!ldiff && !rdiff){
                    line = new_line;
                    return;
                }
            }
            push();
            l->insert_line(left, right, new_line);
            r->insert_line(left, right, new_line);
        }

        // Add the value of the line to everything in [left, right). O(log^2 n).
        void add_affine(int left, int right, Line add) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                line = line + add;
                madd = madd + add;
            } else {
                push();
                l->insert_line(lo, hi, line);
                r->insert_line(lo, hi, line);
                line = Line(0, INF);
                l->add_affine(left, right, add);
                r->add_affine(left, right, add);
            }
        }

        // Get min at x. O(log n).
        ll query(int x){
            assert(lo <= x && x < hi);
            if(!l){
                return line.eval(x);
            }
            push();
            ll rec;
            int mid = lo + (hi - lo) / 2;
            if(x >= mid) {
                rec = r->query(x);
            } else {
                rec = l->query(x);
            }
            return min(line.eval(x), rec);
        }
    };
}

void solve(){
    int n, q;
    cin >> n >> q;
    vi v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    vll diff(n-1);
    for(int i = 0; i < n-1; i++) {
        diff[i] = v[i+1] - v[i];
    }
    debug(diff);

    // breaks at n=1 for some reason lmao
    if(n == 1){
        while(q--){
            int t;
            cin >> t;
            if(t == 1 || t == 2){
                int l, r; ll s, c;
                cin >> l >> r >> s >> c;
            } else {
                int l, r;
                cin >> l >> r;
                cout << 1 << endl;
            }
        }
        return;
    }
    
    lichao::Node* lct = new lichao::Node(0, n);
    for(int i = 0; i < n; i++){
        lct->insert_line(i, i+1, lichao::Line(0, v[i]));
    }
    segtree::Node* st = new segtree::Node(0, n-1, diff);
    
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int l, r; ll s, c;
            cin >> l >> r >> s >> c;
            l--;
            lichao::Line ln = lichao::Line(c, s - c * l);
            lct->add_affine(l, r, ln);
            st->add(l, r, c);
            // debug(lct->query(r) - lct->query(r-1));
            if(l > 0) st->set(l-1, l, lct->query(l) - lct->query(l-1));
            if(r < n) st->set(r-1, r, lct->query(r) - lct->query(r-1));
            debug(st->qout.ans, st->qout.lnum, st->qout.llen, st->qout.rnum, st->qout.rlen, st->qout.same);
        }else if(t == 2){
            int l, r; ll s, c;
            cin >> l >> r >> s >> c;
            l--;
            lichao::Line ln = lichao::Line(c, s - c * l);
            lct->wipe(l, r);
            lct->insert_line(l, r, ln);
            st->set(l, r, c);
            if(l > 0) st->set(l-1, l, lct->query(l) - lct->query(l-1));
            if(r < n) st->set(r-1, r, lct->query(r) - lct->query(r-1));
        }else{
            int l, r;
            cin >> l >> r;
            l--;
            if(l + 1 == r){
                cout << 1 << endl;
            } else {
                segtree::QueryOut qout = st->query(l, r-1);
                debug(qout.ans, qout.lnum, qout.llen, qout.rnum, qout.rlen, qout.same);
                cout << qout.ans + 1 << endl;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

Progression.cpp: In constructor 'segtree::QueryOut::QueryOut(int, ll, int, ll, int, bool, int)':
Progression.cpp:44:13: warning: 'segtree::QueryOut::llen' will be initialized after [-Wreorder]
   44 |         int llen, rlen;
      |             ^~~~
Progression.cpp:43:18: warning:   'll segtree::QueryOut::rnum' [-Wreorder]
   43 |         ll lnum, rnum;
      |                  ^~~~
Progression.cpp:47:9: warning:   when initialized here [-Wreorder]
   47 |         QueryOut(int ans, ll lnum, int llen, ll rnum, int rlen, bool same, int len) : ans(ans), lnum(lnum), llen(llen), rnum(rnum), rlen(rlen), same(same), len(len) {}
      |         ^~~~~~~~

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