Submission #1271789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271789		pvb.tunglam	ZIGZAG (INOI20_zigzag)	C++20	100 / 100	534 ms	71344 KiB

Main

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

struct Node {
    ll first, last; // p[l], p[r]
    int len_p; // number of p elements in segment
    int d_len; // number of d elements = len_p - 1
    ll sum; // total contribution from d runs: sum over runs t*(t+1)/2
    int pref; // length of alternating prefix in d (count of d elements)
    int suff; // length of alternating suffix in d
    int first_sign; // sign of first d element (0 if none)
    int last_sign;  // sign of last d element (0 if none)
    Node() {
        first = last = 0;
        len_p = d_len = 0;
        sum = 0;
        pref = suff = 0;
        first_sign = last_sign = 0;
    }
};
inline int sgnll(ll x){ if(x>0) return 1; if(x<0) return -1; return 0; }
inline ll run_contrib(int t){ return 1LL * t * (t + 1) / 2; }

const int MAXN = 300005;
vector<Node> seg;
vector<ll> lazyAdd;
vector<char> lazyFlip;
int n,q;
vector<ll> a;

Node make_leaf(ll val){
    Node nd;
    nd.first = nd.last = val;
    nd.len_p = 1;
    nd.d_len = 0;
    nd.sum = 0;
    nd.pref = nd.suff = 0;
    nd.first_sign = nd.last_sign = 0;
    return nd;
}

Node mergeNode(const Node &A, const Node &B){
    if(A.len_p == 0) return B;
    if(B.len_p == 0) return A;
    Node R;
    R.len_p = A.len_p + B.len_p;
    R.first = A.first;
    R.last = B.last;
    R.d_len = A.d_len + B.d_len + 1;
    ll total = A.sum + B.sum;
    int s = sgnll(B.first - A.last);

    int left_ext = 0;
    if(A.d_len > 0 && A.suff > 0 && A.last_sign != 0 && s != 0 && A.last_sign * s == -1){
        left_ext = A.suff;
    }
    int right_ext = 0;
    if(B.d_len > 0 && B.pref > 0 && B.first_sign != 0 && s != 0 && s * B.first_sign == -1){
        right_ext = B.pref;
    }
    if(s != 0){
        int combined = left_ext + 1 + right_ext;
        if(left_ext > 0) total -= run_contrib(left_ext);
        if(right_ext > 0) total -= run_contrib(right_ext);
        total += run_contrib(combined);
    }
    R.sum = total;

    if(A.d_len > 0) R.first_sign = A.first_sign;
    else {
        if(s != 0) R.first_sign = s;
        else R.first_sign = B.first_sign;
    }
    if(B.d_len > 0) R.last_sign = B.last_sign;
    else {
        if(s != 0) R.last_sign = s;
        else R.last_sign = A.last_sign;
    }

    // pref
    if(A.d_len == 0){
        if(s == 0){
            R.pref = B.pref;
        } else {
            int ext = 0;
            if(B.d_len > 0 && B.pref > 0 && R.first_sign != 0 && R.first_sign * B.first_sign == -1) ext = B.pref;
            R.pref = 1 + ext;
        }
    } else {
        if(A.pref == A.d_len && s != 0 && A.last_sign * s == -1){
            int ext = 0;
            if(B.d_len > 0 && B.pref > 0 && s * B.first_sign == -1) ext = B.pref;
            R.pref = A.d_len + 1 + ext;
        } else R.pref = A.pref;
    }

    // suff (fixed logic)
    if(B.d_len == 0){
        if(s == 0){
            R.suff = 0;
        } else {
            int ext = 0;
            if(A.d_len > 0 && A.suff > 0 && A.last_sign * s == -1) ext = A.suff;
            R.suff = 1 + ext;
        }
    } else {
        if(B.suff == B.d_len && s != 0 && s * B.first_sign == -1){
            int ext = 0;
            if(A.d_len > 0 && A.suff > 0 && A.last_sign * s == -1) ext = A.suff;
            R.suff = B.d_len + 1 + ext;
        } else R.suff = B.suff;
    }
    return R;
}

void applyAdd(int id, ll v){
    lazyAdd[id] += v;
    seg[id].first += v;
    seg[id].last  += v;
    // signs and sum/pref/suff unchanged
}

void applyFlip(int id){
    lazyFlip[id] ^= 1;
    // composition: flip negates pending add
    lazyAdd[id] = -lazyAdd[id];
    seg[id].first = -seg[id].first;
    seg[id].last  = -seg[id].last;
    // internal d signs are multiplied by -1 => first_sign/last_sign flip sign
    seg[id].first_sign = -seg[id].first_sign;
    seg[id].last_sign  = -seg[id].last_sign;
    // sum/pref/suff unchanged (alternation preserved)
}

void pushDown(int id){
    int lc = id<<1, rc = lc|1;
    if(lc >= (int)seg.size()) return;
    if(lazyFlip[id]){
        applyFlip(lc);
        applyFlip(rc);
        lazyFlip[id] = 0;
    }
    if(lazyAdd[id] != 0){
        applyAdd(lc, lazyAdd[id]);
        applyAdd(rc, lazyAdd[id]);
        lazyAdd[id] = 0;
    }
}

void build(int id, int l, int r){
    lazyAdd[id] = 0;
    lazyFlip[id] = 0;
    if(l==r){
        seg[id] = make_leaf(a[l]);
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    seg[id] = mergeNode(seg[id*2], seg[id*2+1]);
}

void updateAdd(int id, int l, int r, int ql, int qr, ll v){
    if(qr<l || r<ql) return;
    if(ql<=l && r<=qr){
        applyAdd(id, v);
        return;
    }
    pushDown(id);
    int mid=(l+r)/2;
    updateAdd(id*2,l,mid,ql,qr,v);
    updateAdd(id*2+1,mid+1,r,ql,qr,v);
    seg[id] = mergeNode(seg[id*2], seg[id*2+1]);
}

void updateFlip(int id, int l, int r, int ql, int qr){
    if(qr<l || r<ql) return;
    if(ql<=l && r<=qr){
        applyFlip(id);
        return;
    }
    pushDown(id);
    int mid=(l+r)/2;
    updateFlip(id*2,l,mid,ql,qr);
    updateFlip(id*2+1,mid+1,r,ql,qr);
    seg[id] = mergeNode(seg[id*2], seg[id*2+1]);
}

Node queryNode(int id, int l, int r, int ql, int qr){
    if(qr<l || r<ql) return Node();
    if(ql<=l && r<=qr) return seg[id];
    pushDown(id);
    int mid=(l+r)/2;
    Node L = queryNode(id*2,l,mid,ql,qr);
    Node R = queryNode(id*2+1,mid+1,r,ql,qr);
    return mergeNode(L,R);
}

inline long long answer_from_node(const Node &nd){
    return (long long)nd.len_p + nd.sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(!(cin>>n>>q)) return 0;
    a.assign(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    seg.assign(4*(n+5), Node());
    lazyAdd.assign(4*(n+5), 0);
    lazyFlip.assign(4*(n+5), 0);
    build(1,1,n);
    while(q--){
        char t; cin>>t;
        if(t=='*'){
            int l,r; cin>>l>>r;
            updateFlip(1,1,n,l,r);
        } else if(t=='+'){
            int l,r; ll v; cin>>l>>r>>v;
            updateAdd(1,1,n,l,r,v);
        } else if(t=='?'){
            int l,r; cin>>l>>r;
            Node nd = queryNode(1,1,n,l,r);
            cout << answer_from_node(nd) << '\n';
        }
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15