Submission #711825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
711825	2023-03-17T14:44:53 Z	Thienu	Progression (NOI20_progression)	C++17	68 / 100	1771 ms	117228 KB

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

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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	375 ms	112980 KB	Output is correct
2	Correct	233 ms	3588 KB	Output is correct
3	Correct	211 ms	3648 KB	Output is correct
4	Correct	220 ms	3528 KB	Output is correct
5	Correct	225 ms	3548 KB	Output is correct
6	Correct	216 ms	3592 KB	Output is correct
7	Correct	235 ms	3428 KB	Output is correct
8	Correct	2 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	364 ms	115804 KB	Output is correct
12	Correct	409 ms	115684 KB	Output is correct
13	Correct	373 ms	115916 KB	Output is correct
14	Correct	421 ms	116088 KB	Output is correct
15	Correct	371 ms	115912 KB	Output is correct
16	Correct	437 ms	115684 KB	Output is correct
17	Correct	373 ms	115692 KB	Output is correct
18	Correct	371 ms	115644 KB	Output is correct

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	596 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	836 ms	108160 KB	Output is correct
2	Correct	465 ms	996 KB	Output is correct
3	Correct	409 ms	860 KB	Output is correct
4	Correct	423 ms	804 KB	Output is correct
5	Correct	426 ms	960 KB	Output is correct
6	Correct	419 ms	884 KB	Output is correct
7	Correct	436 ms	924 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	902 ms	111776 KB	Output is correct
12	Correct	832 ms	114260 KB	Output is correct
13	Correct	842 ms	112948 KB	Output is correct
14	Correct	879 ms	112864 KB	Output is correct
15	Correct	804 ms	114312 KB	Output is correct
16	Correct	927 ms	114760 KB	Output is correct
17	Correct	882 ms	114668 KB	Output is correct
18	Correct	896 ms	114868 KB	Output is correct
19	Correct	861 ms	114196 KB	Output is correct
20	Correct	840 ms	114272 KB	Output is correct
21	Correct	840 ms	114192 KB	Output is correct

Subtask #4

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1396 ms	107432 KB	Output is correct
2	Correct	320 ms	488 KB	Output is correct
3	Correct	311 ms	536 KB	Output is correct
4	Correct	349 ms	504 KB	Output is correct
5	Correct	308 ms	580 KB	Output is correct
6	Correct	321 ms	596 KB	Output is correct
7	Correct	363 ms	456 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1564 ms	110704 KB	Output is correct
12	Correct	1537 ms	116972 KB	Output is correct
13	Correct	1445 ms	113916 KB	Output is correct
14	Correct	1385 ms	113752 KB	Output is correct
15	Correct	1381 ms	117064 KB	Output is correct
16	Correct	1557 ms	117060 KB	Output is correct
17	Correct	1544 ms	117068 KB	Output is correct
18	Correct	1555 ms	117228 KB	Output is correct
19	Correct	1367 ms	117036 KB	Output is correct
20	Correct	1384 ms	117044 KB	Output is correct
21	Correct	1375 ms	117016 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	836 ms	108160 KB	Output is correct
2	Correct	465 ms	996 KB	Output is correct
3	Correct	409 ms	860 KB	Output is correct
4	Correct	423 ms	804 KB	Output is correct
5	Correct	426 ms	960 KB	Output is correct
6	Correct	419 ms	884 KB	Output is correct
7	Correct	436 ms	924 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	902 ms	111776 KB	Output is correct
12	Correct	832 ms	114260 KB	Output is correct
13	Correct	842 ms	112948 KB	Output is correct
14	Correct	879 ms	112864 KB	Output is correct
15	Correct	804 ms	114312 KB	Output is correct
16	Correct	927 ms	114760 KB	Output is correct
17	Correct	882 ms	114668 KB	Output is correct
18	Correct	896 ms	114868 KB	Output is correct
19	Correct	861 ms	114196 KB	Output is correct
20	Correct	840 ms	114272 KB	Output is correct
21	Correct	840 ms	114192 KB	Output is correct
22	Correct	1659 ms	116648 KB	Output is correct
23	Correct	409 ms	3516 KB	Output is correct
24	Correct	367 ms	3460 KB	Output is correct
25	Correct	391 ms	3468 KB	Output is correct
26	Correct	370 ms	3580 KB	Output is correct
27	Correct	406 ms	3524 KB	Output is correct
28	Correct	394 ms	3668 KB	Output is correct
29	Correct	1 ms	336 KB	Output is correct
30	Correct	2 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1700 ms	113676 KB	Output is correct
33	Correct	1665 ms	116480 KB	Output is correct
34	Correct	1733 ms	113696 KB	Output is correct
35	Correct	1771 ms	113708 KB	Output is correct
36	Correct	1430 ms	113664 KB	Output is correct
37	Correct	1459 ms	113536 KB	Output is correct
38	Correct	1355 ms	113504 KB	Output is correct
39	Correct	1724 ms	116420 KB	Output is correct
40	Correct	1701 ms	116756 KB	Output is correct
41	Correct	1729 ms	116564 KB	Output is correct
42	Correct	1707 ms	116460 KB	Output is correct
43	Correct	1720 ms	116536 KB	Output is correct
44	Correct	1662 ms	116464 KB	Output is correct
45	Correct	1628 ms	116384 KB	Output is correct

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	375 ms	112980 KB	Output is correct
2	Correct	233 ms	3588 KB	Output is correct
3	Correct	211 ms	3648 KB	Output is correct
4	Correct	220 ms	3528 KB	Output is correct
5	Correct	225 ms	3548 KB	Output is correct
6	Correct	216 ms	3592 KB	Output is correct
7	Correct	235 ms	3428 KB	Output is correct
8	Correct	2 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	364 ms	115804 KB	Output is correct
12	Correct	409 ms	115684 KB	Output is correct
13	Correct	373 ms	115916 KB	Output is correct
14	Correct	421 ms	116088 KB	Output is correct
15	Correct	371 ms	115912 KB	Output is correct
16	Correct	437 ms	115684 KB	Output is correct
17	Correct	373 ms	115692 KB	Output is correct
18	Correct	371 ms	115644 KB	Output is correct
19	Incorrect	3 ms	596 KB	Output isn't correct
20	Halted	0 ms	0 KB	-