Submission #832855

#	Time	Username	Problem	Language	Result	Execution time	Memory
832855		_martynas	Progression (NOI20_progression)	C++11	100 / 100	1394 ms	97596 KiB

Progression

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 3e5+5;

struct Node {
    int len = 0;
    ll dl = 0, dr = 0;
    ll diffl = 0, diffr = 0;
    int lenl = 0, lenr = 0, best = 1;
    bool set_tag = false;
    ll s = 0, c = 0;
};

Node merge(Node lhs, Node rhs) {
    Node res{};
    res.best = max(lhs.best, rhs.best);
    ll diff = rhs.dl-lhs.dr;
    res.best = max(res.best, (diff == lhs.diffr ? lhs.lenr : 1)+(diff == rhs.diffl ? rhs.lenl : 1));
    if(lhs.len == 1) lhs.diffl = diff, lhs.lenl = 1;
    if(rhs.len == 1) rhs.diffr = diff, rhs.lenr = 1;
    res.lenl = lhs.lenl + (diff == lhs.diffl && lhs.lenl == lhs.len ? (diff == rhs.diffl ? rhs.lenl : 1) : 0);
    res.lenr = rhs.lenr + (diff == rhs.diffr && rhs.lenr == rhs.len ? (diff == lhs.diffr ? lhs.lenr : 1) : 0);
    res.best = max(res.best, max(res.lenl, res.lenr));

    res.diffl = lhs.diffl, res.diffr = rhs.diffr;
    res.dl = lhs.dl, res.dr = rhs.dr;
    res.len = lhs.len+rhs.len;
    return res;
}

struct Seg {
    vector<Node> n;

    Seg() {
        n.resize(4*mxn);
    }

    void push(Node &chi, Node par) {
        if(par.set_tag) {
            chi.dl = par.s, chi.dr = par.s+(chi.len-1)*par.c;
            chi.diffl = par.c, chi.diffr = par.c;
            chi.lenl = chi.len, chi.lenr = chi.len;
            chi.best = chi.len;
            chi.set_tag = true;
            chi.s = par.s, chi.c = par.c;
        }
        else {
            chi.dl += par.s, chi.dr += par.s+(chi.len-1)*par.c;
            chi.diffl += par.c, chi.diffr += par.c;
            chi.s += par.s, chi.c += par.c;
        }
    }

    void push(int u) {
        Node par = n[u];
        push(n[2*u], par);
        par.s += n[2*u].len*par.c;
        push(n[2*u+1], par);
        n[u].set_tag = false;
        n[u].s = n[u].c = 0;
    }

    void pull(int u) {
        n[u] = merge(n[2*u], n[2*u+1]);
        // printf("merging %d, %d: %d\n", 2*u, 2*u+1, n[u].best);
        // printf("%d: len = %d, dl = %lld, dr = %lld, diffl = %lld, diffr = %lld,\nlenl = %d, lenr = %d, best = %d\n",
        //     2*u, n[2*u].len, n[2*u].dl, n[2*u].dr, n[2*u].diffl, n[2*u].diffr, n[2*u].lenl, n[2*u].lenr, n[2*u].best);
        // printf("%d: len = %d, dl = %lld, dr = %lld, diffl = %lld, diffr = %lld,\nlenl = %d, lenr = %d, best = %d\n",
        //     2*u+1, n[2*u+1].len, n[2*u+1].dl, n[2*u+1].dr, n[2*u+1].diffl, n[2*u+1].diffr, n[2*u+1].lenl, n[2*u+1].lenr, n[2*u+1].best);
        // printf("----------\n");
    }

    void add(int u, int l, int r, int ql, int qr, ll s, ll c) {
        if(r < ql || l > qr) return;
        // printf("add: u = %d, l, r = [%d; %d], ql, qr = [%d; %d], s = %lld, c = %lld,\n", u, l, r, ql, qr, s, c);
        if(ql <= l && r <= qr) {
            if(l == r) n[u].len = 1;
            n[u].s += s, n[u].c += c;
            n[u].dl += s, n[u].dr += s+(n[u].len-1)*c;
            n[u].diffl += c, n[u].diffr += c;
            return;
        }
        push(u);
        int m = (l+r)/2;
        add(2*u, l, m, ql, qr, s, c), add(2*u+1, m+1, r, max(m+1, ql), qr, s+max(0, m-ql+1)*c, c); 
        pull(u);
    }

    void set(int u, int l, int r, int ql, int qr, ll s, ll c) {
        if(r < ql || l > qr) return;
        // printf("set: u = %d, l, r = [%d; %d], ql, qr = [%d; %d], s = %lld, c = %lld,\n", u, l, r, ql, qr, s, c);
        if(ql <= l && r <= qr) {
            if(l == r) n[u].len = 1;
            n[u].set_tag = true;
            n[u].s = s, n[u].c = c;
            n[u].dl = s, n[u].dr = s+(n[u].len-1)*c;
            n[u].diffl = c, n[u].diffr = c;
            n[u].lenl = n[u].len, n[u].lenr = n[u].len;
            n[u].best = n[u].len;
            return;
        }
        push(u);
        int m = (l+r)/2;
        set(2*u, l, m, ql, qr, s, c), set(2*u+1, m+1, r, max(m+1, ql), qr, s+max(0, m-ql+1)*c, c); 
        pull(u);
        // printf("%d: len = %d, dl = %lld, dr = %lld, diffl = %lld, diffr = %lld,\nlenl = %d, lenr = %d, best = %d\n",
        //     u, n[u].len, n[u].dl, n[u].dr, n[u].diffl, n[u].diffr, n[u].lenl, n[u].lenr, n[u].best);
    }

    Node get(int u, int l, int r, int ql, int qr) {
        if(r < ql || l > qr) return {};
        // printf("get: u = %d, l, r = [%d; %d], ql, qr = [%d; %d]\n", u, l, r, ql, qr);
        if(ql <= l && r <= qr) return n[u];
        int m = (l+r)/2;
        push(u);
        Node lhs = get(2*u, l, m, ql, qr);
        Node rhs = get(2*u+1, m+1, r, ql, qr);
        pull(u);
        return (lhs.len == 0 ? rhs : (rhs.len == 0 ? lhs : merge(lhs, rhs)));
    }
} seg;

int n, q;
ll D[mxn];

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> D[i];
    for(int i = 1; i <= n; i++) {
        seg.set(1, 1, n, i, i, D[i], 0);
    }
    for(int i = 0; i < q; i++) {
        ll t, l, r, s, c; cin >> t >> l >> r;
        if(t == 1) {
            cin >> s >> c;
            // for(int j = l; j <= r; j++) D[j] += s+(j-l)*c;
            seg.add(1, 1, n, l, r, s, c);
        }
        else if(t == 2) {
            cin >> s >> c;
            // for(int j = l; j <= r; j++) D[j] = s+(j-l)*c;
            seg.set(1, 1, n, l, r, s, c);
        }
        else {
            // int ans = 1, diff = D[l+1]-D[l], cnt = 1;
            // for(int j = l+1; j <= r; j++) {
            //     if(diff == D[j]-D[j-1]) {
            //         cnt++; ans = max(ans, cnt);
            //     }
            //     else {
            //         diff = D[j]-D[j-1], cnt = 2;
            //     }
            // }
            // cout << ans << "!\n";
            cout << seg.get(1, 1, n, l, r).best << "\n";
        }
        // cerr << "actual:\n";
        // for(int i = 1; i <= n; i++) {
        //     cerr << D[i] << " ";
        // }
        // cerr << "\n";
        // cerr << "got:\n";
        // for(int i = 1; i <= n; i++) {
        //     cerr << seg.get(1, 1, n, i, i).dl << " ";
        // }
        // cerr << "\n";
    }
    return 0;
}

Compilation message (stderr)

Progression.cpp:8:2: warning: #warning change mxn [-Wcpp]
    8 | #warning change mxn
      |  ^~~~~~~

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