Submission #635080

#	Time	Username	Problem	Language	Result	Execution time	Memory
635080		K4YAN	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	951 ms	94248 KiB

Main

//Be Name Khoda

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define all(x) x.begin(), x.end()

const ll mxn = 3e5 + 16, INF = 1e16 + 16;
ll n, t, q, w;
vector<ll> g;
char c;

inline void input() {

    cin >> n >> t;
    for(int i = 0; i < n; i++) {
        cin >> q;
        g.push_back(q);
    }

}

struct item {
    ll sz, ans, L, R, bp, bs, kp, ks;
};
struct segtree {

    int sz = 1;
    item NE = {0, 0, 0, 0, 0, 0, 0, 0};
    vector<item> v;
    vector<ll> lz, ls;

    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, NE);
        lz.assign(2 * sz, 1);
        ls.assign(2 * sz, 0);
        return;
    }
    void shift(int x, int lx, int rx) {
        if(lz[x] == 1 && ls[x] == 0) return;
        if(lz[x] == -1) {
            v[x].L *= -1, v[x].R *= -1;
            swap(v[x].bp, v[x].kp);
            swap(v[x].bs, v[x].ks);
            if(rx - lx > 1) {
                lz[2 * x + 1] *= -1, lz[2 * x + 2] *= -1;
                ls[2 * x + 1] *= -1, ls[2 * x + 2] *= -1;
            } lz[x] = 1;
        } if(ls[x] != 0) {
            v[x].L += ls[x], v[x].R += ls[x];
            if(rx - lx > 1) {
                ls[2 * x + 1] += ls[x], ls[2 * x + 2] += ls[x];
            } ls[x] = 0;
        } return;
    }//Shift Vaghean doroste
    item merge(item a, item b) {
        if(a.sz == 0) return b;
        if(b.sz == 0) return a;
        ll s = a.sz + b.sz, L = a.L, R = b.R, ans = a.ans + b.ans, bp, bs, kp, ks;
        if(a.R == b.L) {
            kp = a.kp, ks = b.ks, bp = a.bp, bs = b.bs;
            return {s, ans, L, R, bp, bs, kp, ks};
        }
        if(a.R > b.L) {
            ans += (1LL * a.bs * b.kp);
            if(a.sz & 1) {
                if(a.sz == a.bp) {
                    bp = a.sz + b.kp, kp = 1;
                } else {
                    bp = a.bp, kp = a.kp;
                }
            } else {
                if(a.sz == a.kp) {
                    kp = a.sz + b.kp, bp = 1;
                } else {
                    bp = a.bp, kp = a.kp;
                }
            }
            if(b.sz & 1) {
                if(b.sz == b.ks) {
                    ks = b.sz + a.bs, bs = 1;
                } else {
                    ks = b.ks, bs = b.bs;
                }
            } else {
                if(b.sz == b.bs) {
                    bs = b.sz + a.bs, ks = 1;
                } else {
                    ks = b.ks, bs = b.bs;
                }
            }
            return {s, ans, L, R, bp, bs, kp, ks};
        }
        if(a.R < b.L) {
            ans += (1LL * a.ks * b.bp);
            if(a.sz & 1) {
                if(a.sz == a.kp) {
                    kp = a.sz + b.bp, bp = 1;
                } else {
                    kp = a.kp, bp = a.bp;
                }
            } else {
                if(a.sz == a.bp) {
                    bp = a.sz + b.bp, kp = 1;
                } else {
                    bp = a.bp, kp = a.kp;
                }
            } 
            if(b.sz & 1) {
                if(b.sz == b.bs) {
                    bs = b.sz + a.ks, ks = 1;
                } else {
                    bs = b.bs, ks = b.ks;
                }
            } else {
                if(b.sz == b.ks) {
                    ks = b.sz + a.ks, bs = 1;
                } else {
                    bs = b.bs, ks = b.ks;
                }
            }
            return {s, ans, L, R, bp, bs, kp, ks};
        }
        return NE;
    }
    void build(vector<ll> &g, int x, int lx, int rx) {
        if(rx - lx == 1) {
            if(lx < int(g.size())) {
                v[x] = {1, 1, g[lx], g[lx], 1, 1, 1, 1};
            } return;
        }
        int m = (lx + rx) >> 1;
        build(g, 2 * x + 1, lx, m), build(g, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return;
    }
    void build(vector<ll> & g) {
        build(g, 0, 0, sz);
        return;
    }
    void zarb(int l, int r, int x, int lx, int rx) {
        shift(x, lx, rx);
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            lz[x] = -1;
            shift(x, lx, rx);
            return;
        } int m = (lx + rx) >> 1;
        zarb(l, r, 2 * x + 1, lx, m);
        zarb(l, r, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return;
    }
    void zarb(int l, int r) {
        zarb(l, r, 0, 0, sz);
        return;
    }
    void jam(int l, int r, int q, int x, int lx, int rx) {
        shift(x, lx, rx);
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            ls[x] += q;
            shift(x, lx, rx);
            return;
        } int m = (lx + rx) >> 1;
        jam(l, r, q, 2 * x + 1, lx, m);
        jam(l, r, q, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return;
    }
    void jam(int l, int r, int q) {
        jam(l, r, q, 0, 0, sz);
        return;
    }
    item ask(int l, int r, int x, int lx, int rx) {
        shift(x, lx, rx);
        if(rx <= l || r <= lx) return NE;
        if(l <= lx && rx <= r) {
            return v[x];
        } int m = (lx + rx) >> 1;
        item ans = ask(l, r, 2 * x + 1, lx, m);
        ans = merge(ans, ask(l, r, 2 * x + 2, m, rx));
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
        return ans;
    } 
    ll ask(int l, int r) {
        return ask(l, r, 0, 0, sz).ans;
    }

}; segtree st;

inline void solve() {

    st.init(n);
    st.build(g);
    for(int i = 0; i < t; i++) {
        cin >> c;
        if(c == '*') {
            cin >> q >> w; q--;
            st.zarb(q, w);
        } else if(c == '+') {
            ll v;
            cin >> q >> w >> v; q--;
            st.jam(q, w, v);
        } else {
            cin >> q >> w; q--;
            cout << st.ask(q, w) << "\n";
        }
    } return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

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