oj.uz

답안 #711825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711825 2023-03-17T14:44:53 Z Thienu Progression (NOI20_progression) C++17
68 / 100
 1771 ms 117228 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -