Submission #795691

#	Time	Username	Problem	Language	Result	Execution time	Memory
795691		MISM06	ZIGZAG (INOI20_zigzag)	C++14	0 / 100	2087 ms	121180 KiB

Main

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

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < int , pii > piii;
typedef pair < ll , ll > pll;
typedef pair < ll , pll > plll;
#define pb  push_back
#define all(x)  x.begin(), x.end()
#define sze     size()
#define F first
#define S second
#define kids    int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1;
#define wall__ cout << "________________________________________\n";

const ll N = 3e5 + 10, mod = 1e9 + 7;

struct node {
    ll ans, vl, vr, pre[2], suf[2], is[2], t, len;
    node () {
        ans = 0; vl = 0; vr = 0; pre[0] = pre[1] = 0; suf[0] = suf[1] = 0; is[0] = is[1] = 0; t = 1;
        len = 0;
    }
    void set_len (int x) {
        len = x; t = len % 2; t ^= 1;
    }
    void merge (node x, node y) {
        len = x.len + y.len;
        set_len(len);
        vl = x.vl; vr = y.vr;
        ans = x.ans + y.ans;
        if (x.vr < y.vl) ans += x.suf[0] * y.pre[0];
        if (x.vr > y.vl) ans += x.suf[1] * y.pre[1];
        
        pre[0] = x.pre[0];
        
        pre[1] = x.pre[1];
        
        suf[0] = y.suf[0];
        
        suf[1] = y.suf[1];

        if (x.vr > y.vl) {
            if (x.t == 0) pre[0] += y.pre[x.t ^ 0 ^ 1] * x.is[0];
            
            if (x.t == 1) pre[1] += y.pre[x.t ^ 1 ^ 1] * x.is[1];
            
            if (y.t == 0) suf[0] += y.is[0] * x.suf[y.t ^ 0 ^ 1];
            
            if (y.t == 1) suf[1] += y.is[1] * x.suf[y.t ^ 1 ^ 1];
        } else if (x.vr < y.vl) {
            if (x.t == 1) pre[0] += y.pre[x.t ^ 0 ^ 1] * x.is[0];
            
            if (x.t == 0) pre[1] += y.pre[x.t ^ 1 ^ 1] * x.is[1];
            
            if (y.t == 1) suf[0] += y.is[0] * x.suf[y.t ^ 0 ^ 1];
            
            if (y.t == 0) suf[1] += y.is[1] * x.suf[y.t ^ 1 ^ 1];
        }
        
        is[0] = is[1] = 0;
        if (x.vr > y.vl) {
            is[x.t] = x.is[x.t] & y.is[1];
        } else if (x.vr < y.vl) {
            is[x.t ^ 1] = x.is[x.t ^ 1] & y.is[0]; 
        }
    }
    void relax (ll x, ll y) {
        if (x == -1) {
            swap(pre[0], pre[1]);
            swap(suf[0], suf[1]);
            vl *= -1;
            vr *= -1;
            swap(is[0], is[1]);
        }
        vl += y;
        vr += y;
    }
    
    void make (ll x) {
        set_len(1);
        vl = x; vr = x;
        pre[0] = pre[1] = 1;
        suf[0] = suf[1] = 1;
        ans = 1;
        is[0] = is[1] = 1;
    }
};

int n, a[N];
struct segtree {
    node seg[N << 2];
    ll la1[N << 2], la2[N << 2];
    void build (int v = 1, int tl = 1, int tr = n) {
        la1[v] = 1; la2[v] = 0;
        if (tl == tr) {
            seg[v].make(a[tl]);
            return;
        } kids;
        build(cl, tl, mid);
        build(cr, mid + 1, tr);
        seg[v].merge(seg[cl], seg[cr]);
    }
    void shift (int v, int tl, int tr) {
        seg[v].relax(la1[v], la2[v]);
        int cl = v << 1, cr = v << 1 | 1;
        if (tl != tr) {
            la1[cl] *= la1[v];
            la2[cl] *= la1[v];
            la2[cl] += la2[v];
            la1[cr] *= la1[v];
            la2[cr] *= la1[v];
            la2[cr] += la2[v];
        }
        la1[v] = 1;
        la2[v] = 0;
    }
    void upd (int s, ll val, int l, int r, int v = 1, int tl = 1, int tr = n) {
        shift(v, tl, tr);
        if (l > r) return;
        if (tl == tr) {
            if (s == 0) la2[v] += val;
            else la1[v] *= -1ll;
            shift(v, tl, tr);
            return;
        } kids
        upd(s, val, l, min(r, mid), cl, tl, mid);
        upd(s, val, max(l, mid + 1), r, cr , mid + 1, tr);
        seg[v].merge(seg[cl], seg[cr]);
    }
    node ask (int l, int r, int v = 1, int tl = 1, int tr = n) {
        shift(v, tl, tr);
        if (l == tl && r == tr) return seg[v];
        kids
        if (r <= mid) return ask(l, r, cl, tl, mid);
        else if (l > mid) return ask(l, r, cr, mid + 1, tr);
        else {
            node res;
            res.merge(ask(l, mid, cl, tl, mid), ask(mid + 1, r, cr, mid + 1, tr));
            return res;
        }
    }
} f;

void solve () {
    
    int q; cin >> n >> q;
    for (int i =1 ; i <= n; i++) cin >> a[i];
    f.build();

    while(q--) {
        char t; cin >> t; int l, r; cin >> l >> r;
        if (t == '?') {
            cout << f.ask(l, r).ans << '\n';
        } else if (t == '+') {
            ll x; cin >> x;
            f.upd(0, x, l, r);
        } else {
            f.upd(1, 0, l, r);
        }
    }
    
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
/*
3 1
1 1 1
? 2 3
*/

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