Submission #1181866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181866		mehmetkagan	Progression (NOI20_progression)	C++20	57 / 100	606 ms	51324 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    ll leftVal, rightVal;
    int prefLen, suffLen, maxLen;
    bool allSame;
};

const int NMAX = 300000;
ll A[NMAX+1];         // difficulties (1-indexed)
ll D[NMAX];           // differences: D[i] = A[i+1]-A[i] for i=1..N-1

// Segment tree arrays
Node seg[4*NMAX];
ll lazyAdd[4*NMAX];      // for additive updates on differences
ll lazySet[4*NMAX];      // for assignment updates on differences (use some flag to indicate assignment pending)
bool pendingSet[4*NMAX];

Node combine(const Node &L, const Node &R) {
    if(L.maxLen == 0) return R;
    if(R.maxLen == 0) return L;
    Node res;
    res.leftVal = L.leftVal;
    res.rightVal = R.rightVal;
    // Initially set prefix and suffix lengths:
    res.prefLen = L.prefLen;
    res.suffLen = R.suffLen;
    res.maxLen = max(L.maxLen, R.maxLen);
    res.allSame = (L.allSame && R.allSame && (L.rightVal == R.leftVal));
    // Try to merge L.suff and R.pref if boundary matches.
    if(L.rightVal == R.leftVal) {
        int merged = L.suffLen + R.prefLen;
        res.maxLen = max(res.maxLen, merged);
        if(L.allSame) res.prefLen = L.prefLen + R.prefLen;
        if(R.allSame) res.suffLen = R.suffLen + L.suffLen;
    }
    return res;
}

void build(int idx, int l, int r) {
    if(l == r) {
        seg[idx].leftVal = D[l];
        seg[idx].rightVal = D[l];
        seg[idx].prefLen = seg[idx].suffLen = seg[idx].maxLen = 1;
        seg[idx].allSame = true;
        return;
    }
    int mid = (l+r)/2;
    build(idx*2, l, mid);
    build(idx*2+1, mid+1, r);
    seg[idx] = combine(seg[idx*2], seg[idx*2+1]);
}

// Utility: apply assignment update on seg[node] for interval [l, r]
void applySet(int idx, int l, int r, ll val) {
    seg[idx].leftVal = seg[idx].rightVal = val;
    seg[idx].prefLen = seg[idx].suffLen = seg[idx].maxLen = (r-l+1);
    seg[idx].allSame = true;
    lazySet[idx] = val;
    pendingSet[idx] = true;
    lazyAdd[idx] = 0; // clear additive lazy
}

// Utility: apply additive update on seg[node] for interval [l, r]
void applyAdd(int idx, int l, int r, ll addVal) {
    seg[idx].leftVal += addVal;
    seg[idx].rightVal += addVal;
    if(pendingSet[idx]) {
        lazySet[idx] += addVal;
    } else {
        lazyAdd[idx] += addVal;
    }
}

void pushDown(int idx, int l, int r) {
    int mid = (l+r)/2;
    int leftChild = idx*2, rightChild = idx*2+1;
    if(pendingSet[idx]) {
        applySet(leftChild, l, mid, lazySet[idx]);
        applySet(rightChild, mid+1, r, lazySet[idx]);
        pendingSet[idx] = false;
        lazySet[idx] = 0;
    }
    if(lazyAdd[idx] != 0) {
        applyAdd(leftChild, l, mid, lazyAdd[idx]);
        applyAdd(rightChild, mid+1, r, lazyAdd[idx]);
        lazyAdd[idx] = 0;
    }
}

void updateRangeSet(int idx, int l, int r, int ql, int qr, ll val) {
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr) {
        applySet(idx, l, r, val);
        return;
    }
    pushDown(idx, l, r);
    int mid = (l+r)/2;
    updateRangeSet(idx*2, l, mid, ql, qr, val);
    updateRangeSet(idx*2+1, mid+1, r, ql, qr, val);
    seg[idx] = combine(seg[idx*2], seg[idx*2+1]);
}

void updateRangeAdd(int idx, int l, int r, int ql, int qr, ll addVal) {
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr) {
        applyAdd(idx, l, r, addVal);
        return;
    }
    pushDown(idx, l, r);
    int mid = (l+r)/2;
    updateRangeAdd(idx*2, l, mid, ql, qr, addVal);
    updateRangeAdd(idx*2+1, mid+1, r, ql, qr, addVal);
    seg[idx] = combine(seg[idx*2], seg[idx*2+1]);
}

Node queryRange(int idx, int l, int r, int ql, int qr) {
    if(ql > r || qr < l) return Node{0,0,0,0,0,true}; // identity; be careful when merging
    if(ql <= l && r <= qr) return seg[idx];
    pushDown(idx, l, r);
    int mid = (l+r)/2;
    Node leftRes = queryRange(idx*2, l, mid, ql, qr);
    Node rightRes = queryRange(idx*2+1, mid+1, r, ql, qr);
    if(leftRes.maxLen == 0) return rightRes;
    if(rightRes.maxLen == 0) return leftRes;
    return combine(leftRes, rightRes);
}

//
// Main – processing operations and queries.
//
// NOTE: In an actual contest solution, you would use fast I/O routines.
// Also, you need to maintain a separate data structure for A so that you can answer point queries (for the boundaries of the difference array) quickly,
// especially when processing rewrite operations. For brevity, these parts are omitted here, but the idea is similar: you can use a lazy segment tree for A as well.
//
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    // Build the difference array
    for (int i = 1; i < N; i++) {
        D[i] = A[i+1] - A[i];
    }
    if(N > 1)
        build(1, 1, N-1);
    
    while(Q--){
        int t;
        cin >> t;
        if(t == 1){
            int L, R;
            ll S, C;
            cin >> L >> R >> S >> C;
            // Update A on [L,R] with add operation:
            // (Implementation for updating A is omitted for brevity.)
            
            // Update differences:
            if(L > 1){
                // D[L-1] increases by S.
                updateRangeAdd(1, 1, N-1, L-1, L-1, S);
            }
            if(R < N){
                // D[R] decreases by S + (R-L)*C.
                updateRangeAdd(1, 1, N-1, R, R, -(S + (ll)(R - L)*C));
            }
            if(L <= R-1){
                // All differences in [L, R-1] add C.
                updateRangeAdd(1, 1, N-1, L, R-1, C);
            }
        } else if(t == 2){
            int L, R;
            ll S, C;
            cin >> L >> R >> S >> C;
            // Rewrite A on [L,R]:
            // (Again, update the A array with an assignment lazy tree; omitted here.)
            
            if(L > 1){
                // New D[L-1] = new A[L] - A[L-1] = S - A[L-1].
                // Retrieve A[L-1] (using your A structure) and then update.
                ll newVal = S; // new A[L]
                // For example, assume we can get A[L-1] in O(logN) time.
                // Here we just use a placeholder.
                ll prevA = A[L-1];
                updateRangeSet(1, 1, N-1, L-1, L-1, S - prevA);
            }
            if(R < N){
                // New D[R] = A[R+1] - new A[R] = A[R+1] - (S + (R-L)*C).
                ll nextA = A[R+1]; // get from A structure
                updateRangeSet(1, 1, N-1, R, R, nextA - (S + (ll)(R-L)*C));
            }
            if(L <= R-1){
                // Set differences in [L, R-1] to constant C.
                updateRangeSet(1, 1, N-1, L, R-1, C);
            }
        } else if(t == 3){
            int L, R;
            cin >> L >> R;
            if(L == R) {
                cout << 1 << "\n";
            } else {
                // Query differences in [L, R-1]
                Node ans = queryRange(1, 1, N-1, L, R-1);
                // Answer is max constant differences length + 1.
                cout << ans.maxLen + 1 << "\n";
            }
        }
    }
    return 0;
}

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