Submission #337295

#	Time	Username	Problem	Language	Result	Execution time	Memory
337295		ryangohca	Progression (NOI20_progression)	C++17	100 / 100	2278 ms	86092 KiB

Progression

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define tpip tuple<pii, int, pii>
using namespace std;
struct node{
    int s, e, m, sum, maxcos, lazyset, lazyadd;
    bool lazyseton;
    pii pref, suff;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), maxcos(0), lazyset(-1), lazyadd(0), sum(0), lazyseton(false){
        if (s != e){
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void value(){
        if (lazyseton){
            pref = suff = pii(lazyset+lazyadd, e-s+1);
            sum = (lazyset + lazyadd) * (e-s+1);
            if (s!=e){
                l->lazyset = r->lazyset = lazyset;
                l->lazyadd = r->lazyadd = lazyadd;
                l->lazyseton = r->lazyseton = true;
            }
            lazyadd = 0;
            lazyset = -1;
            lazyseton = false;
            maxcos = e - s + 1;
        } else {
            pref.first += lazyadd;
            suff.first += lazyadd;
            sum += lazyadd * (e-s+1);
            if (s != e){
                l->lazyadd += lazyadd;
                r->lazyadd += lazyadd;
            }
            lazyadd = 0;
        }
    }
    tpip merge_child(tpip lft, tpip rgt, int lftlen, int rgtlen, bool upd = true){
        if (s==e) return tpip(pref, maxcos, suff);
        pii pref, suff;
        int maxcos = 1;
        auto [lpref, lmaxcos, lsuff] = lft;
        auto [rpref, rmaxcos, rsuff] = rgt;
        if (lpref == lsuff && lpref.first == rpref.first && lpref.second == lftlen){
            pref = pii(lpref.first, lpref.second + rpref.second);
        } else {
            pref = lpref;
        }
        if (rpref == rsuff && lsuff.first == rpref.first && rsuff.second == rgtlen){
            suff = pii(lsuff.first, lsuff.second + rpref.second);
        } else {
            suff = rsuff;
        }
        if (lsuff.first == rpref.first){
            maxcos = lsuff.second + rpref.second;
        }
        maxcos = max({maxcos, pref.second, suff.second, lmaxcos, rmaxcos});
        if (upd){
            this->pref = pref;
            this->suff = suff;
            this->maxcos = maxcos;
        }
        return tpip(pref, maxcos, suff);
    }
    void add(int x, int y, int val){
        value();
        if (s==x && e==y){
            lazyadd += val;
            value();
            return;
        }
        if (y <= m) l->add(x, y, val);
        else if (x > m) r->add(x, y, val);
        else l->add(x, m, val), r->add(m+1, y, val);
        l->value(); r->value();
        tpip lft = tpip(l->pref, l->maxcos, l->suff);
        tpip rgt = tpip(r->pref, r->maxcos, r->suff);
        merge_child(lft, rgt, l->e - l->s + 1, r->e - r->s + 1);
        sum = l->sum + r->sum;
    }
    void set(int x, int y, int val){
        value();
        if (s==x && e==y){
            lazyset = val;
            lazyseton = true;
            value();
            return;
        }
        if (y <= m) l->set(x, y, val);
        else if (x > m) r->set(x, y, val);
        else l->set(x, m, val), r->set(m+1, y, val);
        l->value(); r->value();
        tpip lft = tpip(l->pref, l->maxcos, l->suff);
        tpip rgt = tpip(r->pref, r->maxcos, r->suff);
        merge_child(lft, rgt, l->e - l->s + 1, r->e - r->s + 1);
        sum = l->sum + r->sum;
    }
    tpip query(int x, int y){
        value();
        if (s==x && e==y){
            return tpip(pref, maxcos, suff);
        }
        if (y <= m) return l->query(x, y);
        else if (x > m) return r->query(x, y);
        else {
            tpip lft = l->query(x, m);
            tpip rgt = r->query(m+1, y);
            tpip ans = merge_child(lft, rgt, m-x+1, y-(m+1)+1, false);
            return ans;
        }
    }
    int maxplayable(int x, int y){
        tpip ans = query(x, y);
        return get<1>(ans);
    }
    int range_sum(int x, int y){
        value();
        if (s==x && e==y) return sum;
        else if (y <= m) return l->range_sum(x, y);
        else if (x > m) return r->range_sum(x, y);
        else return l->range_sum(x, m) + r->range_sum(m+1, y);
    }
} *root;
main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    int st; cin >> st;
    int pref = st;
    if (n != 1) root = new node(0, n-2);
    for (int i = 0; i < n - 1; i++){
        int g; cin >> g;
        root->set(i, i, g-pref);
        pref = g;
    }
    for (int i = 0; i < q; i++){
        int t; cin >> t;
        if (t==3){
            int a, b; cin >> a >> b; a--; b--;
            if (a == b) cout << "1\n";
            else cout << root->maxplayable(a, b-1) + 1 << '\n';
        } else if (t==2){
            int l, r, s, c; cin >> l >> r >> s >> c;
            if (n==1) continue;
            l--; r--;
            int prev = -1, aft = -1;
            bool prevset = false, aftset = false;
            if (l != 0){
                if (l==1) prev = st, prevset = true;
                else prev = st + root->range_sum(0, l-2), prevset = true;
            }
            if (r!=n-1) aft = st + root->range_sum(0, r), aftset = true;
            int e = s + (r-l) * c;
            if (prevset) root->set(l-1, l-1, s-prev);
            if (aftset) root->set(r, r, aft-e);
            if (l != r) root->set(l, r-1, c);
            if (l==0) st = s;
        } else {
            int l, r, s, c; cin >> l >> r >> s >> c;
            if (n==1) continue;
            l--; r--;
            if (l != 0) root->add(l-1, l-1, s);
            if (r != n-1) root->add(r, r, -(s + (r-l)*c));
            if (l != r) root->add(l, r-1, c);
            if (l == 0) st += s;
        }
    }
}

Compilation message (stderr)

Progression.cpp: In constructor 'node::node(long long int, long long int)':
Progression.cpp:7:40: warning: 'node::lazyadd' will be initialized after [-Wreorder]
    7 |     int s, e, m, sum, maxcos, lazyset, lazyadd;
      |                                        ^~~~~~~
Progression.cpp:7:18: warning:   'long long int node::sum' [-Wreorder]
    7 |     int s, e, m, sum, maxcos, lazyset, lazyadd;
      |                  ^~~
Progression.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), maxcos(0), lazyset(-1), lazyadd(0), sum(0), lazyseton(false){
      |     ^~~~
Progression.cpp: At global scope:
Progression.cpp:127:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main(){
      |      ^

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