Submission #336646

#	Time	Username	Problem	Language	Result	Execution time	Memory
336646		monkey8	Progression (NOI20_progression)	C++14	100 / 100	1653 ms	83180 KiB

Progression

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdio>
#include <utility> 
#include <queue>
#include <math.h>
#include <set>
#include <bitset>
#include <cmath>
#include <bitset>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 300010;
struct node {
    int maxleft, maxright, maxtot;
    ll kleft, kright, valleft, valright;
} st[MAXN << 2];
ll lazy[MAXN << 2];
int lazyClear[MAXN << 2];
ll lazyS[MAXN << 2];
ll lazyC[MAXN << 2];
ll val[MAXN];
int left(int p) {
    return (p << 1);
}
int right(int p) {
    return (p << 1) + 1;
}
node merge(node p1, int l1, int r1, node p2, int l2, int r2) {
    node newNode = node{p1.maxleft, p2.maxright, max(p1.maxtot, max(p2.maxtot, 2)), p1.kleft, p2.kright, p1.valleft, p2.valright};
    int num1 = r1 - l1 + 1;
    int num2 = r2 - l2 + 1;
    if(num1 == p1.maxleft) {
        if(p1.maxleft == 1 && p2.maxleft == 1) {
            newNode.maxleft = 2;
            newNode.kleft = p2.valleft - p1.valright;
        }
        else if(p1.maxleft == 1) {
            if(p2.valleft - p1.valright == p2.kleft) {
                newNode.maxleft = 1 + p2.maxleft;
                newNode.kleft = p2.kleft;
            }
            else {
                newNode.maxleft = 2;
                newNode.kleft = p2.valleft - p1.valright;
            }
        }
        else if(p2.maxleft == 1) {
            if(p2.valleft - p1.valright == p1.kleft) {
                newNode.maxleft = p1.maxleft + 1;
                newNode.kleft = p1.kleft;
            }
        }
        else {
            if(p1.kleft == p2.kleft && p2.valleft - p1.valright == p1.kleft) {
                newNode.maxleft = p1.maxleft + p2.maxleft;
                newNode.kleft = p1.kleft;
            }
            else if(p2.valleft - p1.valright == p1.kleft) {
                newNode.maxleft = p1.maxleft + 1;
                newNode.kleft = p1.kleft;
            }
        }
    }
    if(num2 == p2.maxright) {
        if(p1.maxright == 1 && p2.maxright == 1) {
            newNode.maxright = 2;
            newNode.kright = p2.valleft - p1.valright;
        }
        else if(p1.maxright == 1) {
            if(p2.valleft - p1.valright == p2.kright) {
                newNode.maxright = 1 + p2.maxright;
                newNode.kright = p2.kright;
            }
        }
        else if(p2.maxright == 1) {
            if(p2.valleft - p1.valright == p1.kright) {
                newNode.maxright = p1.maxright + 1;
                newNode.kright = p1.kright;
            }
            else {
                newNode.maxright = 2;
                newNode.kright = p2.valleft - p1.valright;
            }
        }
        else {
            if(p1.kright == p2.kright && p2.valleft - p1.valright == p1.kright) {
                newNode.maxright = p1.maxright + p2.maxright;
                newNode.kright = p1.kright;
            }
            else if(p2.valleft - p1.valright == p2.kright) {
                newNode.maxright = 1 + p2.maxright;
                newNode.kright = p2.kright;
            }
        }
    }
    if(p1.maxright == 1 && p2.maxleft == 1) newNode.maxtot = max(newNode.maxtot, 2);
    else if(p1.maxright == 1) {
        if(p2.valleft - p1.valright == p2.kleft) newNode.maxtot = max(newNode.maxtot, 1 + p2.maxleft);
    }
    else if(p2.maxleft == 1) {
        if(p2.valleft - p1.valright == p1.kright) newNode.maxtot = max(newNode.maxtot, p1.maxright + 1);
    }
    else {
        if(p1.kright == p2.kleft && p2.valleft - p1.valright == p1.kright) newNode.maxtot = max(newNode.maxtot, p1.maxright + p2.maxleft);
        else if(p2.valleft - p1.valright == p1.kright) newNode.maxtot = max(newNode.maxtot, p1.maxright + 1);
        else if(p2.valleft - p1.valright == p2.kleft) newNode.maxtot = max(newNode.maxtot, 1 + p2.maxleft);
    }
    return newNode;
}
void build(int p, int L, int R) {
    if(L == R) st[p] = node{1, 1, 1, 0, 0, val[L], val[R]};
    else {
        build(left(p), L, (L + R)/2);
        build(right(p), (L + R)/2 + 1, R);
        st[p] = merge(st[left(p)], L, (L + R)/2, st[right(p)], (L + R)/2 + 1, R);
    }
}
void push(int p, int L, int R) {
    if(lazyClear[p] == 1) st[p] = node{R - L + 1, R - L + 1, R - L + 1, 0, 0, 0, 0};
    st[p].valleft += lazyS[p] + lazyC[p] * (ll)L;
    st[p].valright += lazyS[p] + lazyC[p] * (ll)R;
    st[p].kleft += lazyC[p];
    st[p].kright += lazyC[p];
    if(L != R) {
        if(lazyClear[p] == 1) {
            lazyClear[left(p)] = 1;
            lazyClear[right(p)] = 1;
            lazyS[left(p)] = 0;
            lazyC[left(p)] = 0;
            lazyS[right(p)] = 0;
            lazyC[right(p)] = 0;
        }
        lazyS[left(p)] += lazyS[p];
        lazyC[left(p)] += lazyC[p];
        lazyS[right(p)] += lazyS[p];
        lazyC[right(p)] += lazyC[p];
    }
    lazyClear[p] = 0;
    lazyS[p] = 0;
    lazyC[p] = 0;
}
void update(int p, int L, int R, int i, int j, ll valS, ll valC) {
    push(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazyS[p] = valS;
        lazyC[p] = valC;
        push(p, L, R);
        return;
    }
    update(left(p), L, (L + R)/2, i, j, valS, valC);
    update(right(p), (L + R)/2 + 1, R, i, j, valS, valC);
    st[p] = merge(st[left(p)], L, (L + R)/2, st[right(p)], (L + R)/2 + 1, R);
}
void updateClear(int p, int L, int R, int i, int j) {
    push(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazyS[p] = 0;
        lazyC[p] = 0;
        lazyClear[p] = 1;
        push(p, L, R);
        return;
    }
    updateClear(left(p), L, (L + R)/2, i, j);
    updateClear(right(p), (L + R)/2 + 1, R, i, j);
    st[p] = merge(st[left(p)], L, (L + R)/2, st[right(p)], (L + R)/2 + 1, R);
}
node query(int p, int L, int R, int i, int j) {
    push(p, L, R);
    if(i > R || j < L) return node{-1, 0, 0, 0, 0, 0, 0};
    if(L >= i && R <= j) return st[p];
    node p1 = query(left(p), L, (L + R)/2, i, j);
    node p2 = query(right(p), (L + R)/2 + 1, R, i, j);
    if(p1.maxleft == -1) return p2; 
    if(p2.maxleft == -1) return p1;
    return merge(p1, L, (L + R)/2, p2, (L + R)/2 + 1, R);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, q; cin >> n >> q;
    for(int i = 0; i < n; i++)
        cin >> val[i];
    build(1, 0, n - 1);
    for(int i = 0; i < q; i++) {
        int x; cin >> x;
        if(x == 3) {
            int l, r; cin >> l >> r;
            cout << query(1, 0, n - 1, l - 1, r - 1).maxtot << '\n';
        }
        else {
            int l, r; ll s, c; cin >> l >> r >> s >> c;
            if(x == 2) updateClear(1, 0, n - 1, l - 1, r - 1);
            update(1, 0, n - 1, l - 1, r - 1, s - (ll)(l - 1) * c, c);
        }
    }
}

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