제출 #335644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335644		ryangohca	Progression (NOI20_progression)	C++17	0 / 100	2051 ms	68936 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;
    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){
        if (s != e){
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void value(){
        if (lazyset != -1){
            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;
            }
            lazyadd = 0;
            lazyset = -1;
            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, bool upd = true){
        if (s==e) return tpip(pref, maxcos, suff);
        pii pref, suff;
        int maxcos = 2;
        auto [lpref, lmaxcos, lsuff] = lft;
        auto [rpref, rmaxcos, rsuff] = rgt;
        if (lpref == lsuff && lpref.first == rpref.first){
            pref = pii(lpref.first, lpref.second + rpref.second);
        } else {
            pref = lpref;
        }
        if (rpref == rsuff && lsuff.first == rpref.first){
            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;
            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);
        sum = l->sum + r->sum;
    }
    void set(int x, int y, int val){
        value();
        if (s==x && e==y){
            lazyset = val;
            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);
        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, 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(){
    int n, q; cin >> n >> q;
    int st; cin >> st;
    int pref = st;
    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;
            l--; r--;
            int prev = -1, aft = -1;
            if (l == 0) st = s;
            else if (l==1) prev = st;
            else prev = st + root->range_sum(0, l-2);
            if (r!=n-1) aft = st + root->range_sum(0, r);
            int e = s + (r-l) * c;
            if (prev != -1) root->set(l-1, l-1, s-prev);
            if (aft != -1) root->set(r, r, aft-e);
            if (l != r) root->set(l, r-1, c);
        } else {
            int l, r, s, c; cin >> l >> r >> s >> c;
            l--; r--;
            if (l == 0) st += s;
            else 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);
        }
        /*
        for (int i = 0; i < n; i++){
            if (i==0) cout << st << ' ';
            else cout << st + root->range_sum(0, i-1) << ' ';
        }
        cout << endl;
        */
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Progression.cpp:121:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main(){
      |      ^

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