제출 #1300118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300118		adaawf	Progression (NOI20_progression)	C++20	68 / 100	715 ms	78148 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
struct PROG {
    long long int x, y, a, b;
    int s, c, d, res;
} t[1200005];
long long int a[300005], lazy[1200005], lazy2[1200005], lazy3[1200005];
PROG Merge(PROG aa, PROG bb) {
    if (aa.s == 0) return bb;
    if (bb.s == 0) return aa;
    PROG res;
    res.x = aa.x; res.y = bb.y;
    res.s = aa.s + bb.s;
    res.a = aa.a; res.b = bb.b;
    if (aa.s == 1) res.a = bb.x - aa.y;
    else res.a = aa.a;
    if (bb.s == 1) res.b = bb.x - aa.y;
    else res.b = bb.b;
    if (res.s == 2) {
        res.res = res.c = res.d = 1;
        return res;
    }
    res.res = max(aa.res, bb.res);
    long long int h = bb.x - aa.y;
    int c = 1;
    if (h == aa.b) c += aa.d;
    if (h == bb.a) c += bb.c;
    //cout << aa.d << " " << bb.c << " " << c << '\n';
    res.res = max(res.res, c);
    if (aa.s == 1) res.c = c;
    else {
        res.c = aa.c;
        if (aa.c == aa.s - 1 && aa.a == h) {
            res.c++;
            if (bb.a == aa.a) {
                res.c += bb.c;
            }
        }
    }
    if (bb.s == 1) res.d = c;
    else {
        res.d = bb.d;
        if (bb.d == bb.s - 1 && bb.b == h) {
            res.d++;
            if (bb.b == aa.b) {
                res.d += aa.d;
            }
        }
    }
    return res;
}
void apply(int v, int tl, int tr, long long int x, long long int y, long long int z) {
    if (z >= -1e12) {
        t[v].x = t[v].y = z;
        t[v].a = t[v].b = 0;
        t[v].c = t[v].d = t[v].res = t[v].s - 1;
        lazy[v] = lazy2[v] = 0;
        lazy3[v] = x;
    }
    t[v].x += x + y * tl;
    t[v].y += x + y * tr;
    t[v].a += y;
    t[v].b += y;
    lazy[v] += x;
    lazy2[v] += y;
}
void push(int v, int tl, int tr) {
    int mid = (tl + tr) >> 1;
    apply(v << 1, tl, mid, lazy[v], lazy2[v], lazy3[v]);
    apply(v << 1 | 1, mid + 1, tr, lazy[v], lazy2[v], lazy3[v]);
    lazy3[v] = -1e18;
    lazy[v] = lazy2[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, long long int x, long long int y) {
    if (l > r) return;
    if (tl == l && tr == r) {
        apply(v, tl, tr, x, y, -1e18);
        return;
    }
    push(v, tl, tr);
    int mid = (tl + tr) >> 1;
    update(v << 1, tl, mid, l, min(r, mid), x, y);
    update(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x, y);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
void update2(int v, int tl, int tr, int l, int r, long long int x, long long int y) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v].s = r - l + 1;
        apply(v, tl, tr, 0, y, x);
        if (tl == tr) {
            t[v].a = t[v].b = 1e18;
        }
        return;
    }
    push(v, tl, tr);
    int mid = (tl + tr) >> 1;
    update2(v << 1, tl, mid, l, min(r, mid), x, y);
    update2(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x, y);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
    //PROG h = t[v];
    //cout << h.x << " " << h.y << " " << h.a << " " << h.b << " " << h.c << " " << h.d << " " << h.res << " " << tl << " " << tr << '\n';
}
PROG sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return {0, 0, 0, 0, 0, 0, 0, 0};
    if (tl == l && tr == r) return t[v];
    push(v, tl, tr);
    int mid = (tl + tr) >> 1;
    PROG h = Merge(sum(v << 1, tl, mid, l, min(r, mid)), sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
    return h;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update2(1, 1, n, i, i, a[i], 0);
    }
    for (int jj = 0; jj < q; jj++) {
        long long int w, x, y, s, c;
        cin >> w >> x >> y;
        if (w == 1) {
            cin >> s >> c;
            update(1, 1, n, x, y, s - x * c, c);
        }
        else if (w == 2) {
            cin >> s >> c;
            update2(1, 1, n, x, y, s - x * c, c);
        }
        else {
            cout << sum(1, 1, n, x, y).res + 1 << '\n';
        }
    }
}

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