Submission #593003

#	Time	Username	Problem	Language	Result	Execution time	Memory
593003		radal	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	903 ms	80516 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2")
//#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 3e5+5,mod = 1e9+7,inf = 1e9+10,base = 211;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
   // if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int n,za[N*4],a[N];
ll lz[N*4],seg[N*4][7]; // val l val r pre ^ pre ! suf ^ suf ! ans
inline void calc(int l,int r,int v){
    int u = (v << 1),m = (l+r) >> 1;
    seg[v][0] = seg[u][0];
    seg[v][1] = seg[u|1][1];
    seg[v][6] = seg[u][6]+seg[u|1][6];
    seg[v][2] = seg[u][2];
    seg[v][3] = seg[u][3];
    seg[v][4] = seg[u|1][4];
    seg[v][5] = seg[u|1][5];
    if (seg[u][1] == seg[u|1][0]) return;
    if (seg[u][1] < seg[u|1][0]){
        seg[v][6] += seg[u][5]*seg[u|1][3];
        if (seg[u][2] == m-l && ((m-l)&1))
            seg[v][2] += seg[u|1][3];
        if (seg[u][3] == m-l && ((m-l)&1) == 0)
            seg[v][3] += seg[u|1][3];
        if (seg[u|1][4] == r-m && ((r-m)&1))
            seg[v][4] += seg[u][5];
        if (seg[u|1][5] == r-m && ((r-m)&1) == 0)
            seg[v][5] += seg[u][5];
        return;
    }
    seg[v][6] += seg[u][4]*seg[u|1][2];
    if (seg[u][2] == m-l && ((m-l)&1) == 0)
        seg[v][2] += seg[u|1][2];
    if (seg[u][3] == m-l && ((m-l)&1))
        seg[v][3] += seg[u|1][2];
    if (seg[u|1][4] == r-m && ((r-m)&1) == 0)
        seg[v][4] += seg[u][4];
    if (seg[u|1][5] == r-m && ((r-m)&1))
        seg[v][5] += seg[u][4];
}
void build(int l,int r,int v = 1){
    za[v] = 1;
    if (r-l == 1){
        seg[v][0] = seg[v][1] = a[l];
        seg[v][2] = seg[v][3] = seg[v][4] = seg[v][5] = seg[v][6] = 1;
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    build(l,m,u);
    build(m,r,u|1);
    calc(l,r,v);
}
inline void passza(int v){
    za[v] *= -1;
    lz[v] *= -1;
    seg[v][0] *= -1;
    seg[v][1] *= -1;
    swap(seg[v][2],seg[v][3]);
    swap(seg[v][4],seg[v][5]);
}
inline void passlz(int v){
    int u = (v << 1);
    lz[u] += lz[v];
    lz[u|1] += lz[v];
    seg[u][0] += lz[v];
    seg[u][1] += lz[v];
    seg[u|1][0] += lz[v];
    seg[u|1][1] += lz[v];
    lz[v] = 0;
}
void upd1(int l,int r,int s,int e,int v){
    if (s >= r || l >= e) return;
    if (s <= l && r <= e){
        passza(v);
        return;
    }
    int u = (v << 1),m = (l+r) >> 1;
    if(za[v] == -1){
        za[v] = 1;
        passza(u);
        passza(u|1);
    }
    if (lz[v])
        passlz(v);
    upd1(l,m,s,e,u);
    upd1(m,r,s,e,u|1);
    calc(l,r,v);
}
void upd2(int l,int r,int s,int e,int x,int v){
    if (s >= r || l >= e) return;
    if (s <= l && r <= e){
        lz[v] += x;
        seg[v][0] += x;
        seg[v][1] += x;
        return;
    }
    int u = (v << 1),m = (l+r) >> 1;
    if(za[v] == -1){
        za[v] = 1;
        passza(u);
        passza(u|1);
    }
    if (lz[v])
        passlz(v);
    upd2(l,m,s,e,x,u);
    upd2(m,r,s,e,x,u|1);
    calc(l,r,v);
}
vector<ll> que(int l,int r,int s,int e,int v = 1){
    vector<ll> ans;
    if (l == s && r == e){
        rep(i,0,7) ans.pb(seg[v][i]);
        return ans;
    }
    int u = (v << 1),m = (l+r) >> 1;
    if(za[v] == -1){
        za[v] = 1;
        passza(u);
        passza(u|1);
    }
    if (lz[v])
        passlz(v);
    if (e <= m) return que(l,m,s,e,u);
    if (s >= m) return que(m,r,s,e,u|1);
    vector<ll> v1,v2;
    v1 = que(l,m,s,m,u);
    v2 = que(m,r,m,e,u|1);
    ans.resize(7);
    ans[0] = v1[0];
    ans[1] = v2[1];
    ans[2] = v1[2];
    ans[3] = v1[3];
    ans[4] = v2[4];
    ans[5] = v2[5];
    ans[6] = v1[6]+v2[6];
    if (v1[1] == v2[0])
        return ans;
    if (v1[1] < v2[0]){
        ans[6] += v1[5]*v2[3];
        if (v1[2] == m-s && ((m-s)&1))
            ans[2] += v2[3];
        if (v1[3] == m-s && ((m-s)&1) == 0)
            ans[3] += v2[3];
        if (v2[4] == e-m && ((e-m)&1))
            ans[4] += v1[5];
        if (v2[5] == e-m && ((e-m)&1) == 0)
            ans[5] += v1[5];
        return ans;
    }
    ans[6] += v1[4]*v2[2];
    if (v1[2] == m-s && ((m-s)&1) == 0)
        ans[2] += v2[2];
    if (v1[3] == m-s && ((m-s)&1))
        ans[3] += v2[2];
    if (v2[4] == e-m && ((e-m)&1) == 0)
        ans[4] += v1[4];
    if (v2[5] == e-m && ((e-m)&1))
        ans[5] += v1[4];
    return ans;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n >> q;
    rep(i,0,n) cin >>a[i];
    build(0,n,1);
    while (q--){
        char c;
        int l,r;
        cin >> c >> l >> r;
        l--;
        if (c == '*'){
            upd1(0,n,l,r,1);
            continue;
        }
        if (c == '+'){
            int x;
            cin >> x;
            upd2(0,n,l,r,x,1);
            continue;
        }
        vector<ll> ans = que(0,n,l,r,1);
        cout << ans[6] << endl;
    }
    return 0;
}

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