Submission #1259111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259111		mohammadsam	ZIGZAG (INOI20_zigzag)	C++20	100 / 100	480 ms	72460 KiB

Main

/*
    in the name of god
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 3e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , q;
int arr[N],b[N];
int V ;
struct node{
    int sum,ans,lazy,beg,last,mxpre,mxsuf,ln;
    node(){}
};
inline bool valid(int a,int b){
    return (min(a,b) < 0 and max(a,b) > 0);
}
node seg[N<<2];
inline node merge(const node& a,const node& b){
    node ans;
    ans.lazy = 1;
    ans.beg = a.beg;
    ans.last = b.last;
    ans.sum = a.sum + b.sum;
    ans.mxpre = ((a.mxpre == a.ln and valid(a.last,b.beg)) ? a.mxpre + b.mxpre  : a.mxpre);
    ans.mxsuf = ((b.mxsuf == b.ln and valid(a.last,b.beg)) ? b.mxsuf + a.mxsuf : b.mxsuf);
    ans.ln = a.ln + b.ln;
    ans.ans = a.ans + b.ans;
    if(valid(a.last,b.beg)){
        ans.ans += (a.mxsuf * b.mxpre);
    }
    return ans;
}
inline void shift(int u){
    seg[u].beg *= -1;
    seg[u].last *= -1;
    seg[u].lazy *= -1;
    seg[u].sum *= -1;
}
inline void relax(int u){
    if(seg[u].lazy == -1){
        shift(lid);shift(rid);
    }
    seg[u].lazy = 1;
}
void build(int u=1,int l=0,int r=n){
    if(r-l==1){
        seg[u].ans = (b[l] != 0);
        seg[u].sum = b[l];
        seg[u].lazy = 1;
        seg[u].beg = seg[u].last = b[l];
        seg[u].mxpre = seg[u].mxsuf = (b[l] != 0);
        seg[u].ln = 1;
        return;
    }
    int mid = (l+r)>>1;
    build(lid,l,mid);
    build(rid,mid,r);
    seg[u] = merge(seg[lid],seg[rid]);
}
void update(int i,int v,int u=1,int l=0,int r=n){
    if(r-l==1){
        seg[u].ans = (v != 0);
        seg[u].sum = v;
        seg[u].beg = seg[u].last = v;
        seg[u].mxpre = seg[u].mxsuf = (v != 0);
        return;
    }
    int mid = (l+r)>>1;
    relax(u);
    if(i < mid) update(i,v,lid,l,mid);
    else update(i,v,rid,mid,r);
    seg[u] = merge(seg[lid],seg[rid]);
}
void Upd(int s,int e,int u=1,int l=0,int r=n){
    if(e <= s || e <= l || r <= s) return;
    if(s <= l and r <= e){
        shift(u);
        return;
    }
    int mid = (l+r)>>1;
    relax(u);
    Upd(s,e,lid,l,mid);
    Upd(s,e,rid,mid,r);
    seg[u] = merge(seg[lid],seg[rid]);
}
node get(int s,int e,int u=1,int l=0,int r=n){
    if(s <= l and r <= e) return seg[u];
    int mid = (l+r)>>1;
    relax(u);
    if(e <= mid) return get(s,e,lid,l,mid);
    if(s >= mid) return get(s,e,rid,mid,r);
    return merge(get(s,e,lid,l,mid),get(s,e,rid,mid,r));
}
struct Brut{
    int arr2[LOG];
    void init(){
        for(int i =1 ;i<=n;i++) arr2[i] = arr[i];
    }
    void add(int l,int r,int v){
        for(int i = l;i <= r;i++) arr2[i] += v;
    }
    void mul(int l,int r){
        for(int i = l; i <= r;i++) arr2[i] = (-arr2[i]);
    }
    int get(int l,int r){
        int ans = r-l+1;
        for(int l1 = l;l1 <= r;l1++){
            if(l1 + 1 <= r and arr2[l1+1] != arr2[l1]) ans++;
            for(int r1 = l1+2;r1 <= r;r1++){
                if(valid(arr2[r1-1]-arr2[r1-2],arr2[r1] - arr2[r1-1])) ans++;
                else break;
            }
        }
        return ans;
    }
} bt;
inline int ask(int x){ return (x == 0 ? 0 :  get(0,x).sum);}
inline void Add(int s,int e,int v){
    //bt.add(s,e,v)
    update(s-1,get(s-1,s).last + v);
    if(e < n+1){
        update(e-1,get(e-1,e).last -v);
    }
}
inline void Mul(int s,int e){
    int x2,y2;
    bool c2=0;
    if( e < n+1){
        c2 = 1;
        x2 = ask(e);
        y2 = ask(e-1);
    }
    update(s-1,-ask(s) - ask(s-1));
    if(c2) update(e-1,x2+y2);
    if(s < e-1) Upd(s,e-1);
}

int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> q;
    for(int i =1;i<=n;i++) cin >> arr[i];
    if(n <= 10){
        bt.init();
        for(int i = 1;i<=q;i++){
            string c;
            int l,r,x;
            cin >> c >>  l >> r;
            if(c[0] == '+'){
                cin >> x;
                bt.add(l,r,x);
            }
            else if(c[0] == '?') cout << bt.get(l,r) << endl;
            else bt.mul(l,r);
        }
        return 0;
    }
    for(int i = 0;i<n;i++) b[i] = arr[i+1] - arr[i];
    build();
    for(int i = 1;i<= q;i++){
        string s;
        cin >> s;
        int l,r;
        cin >> l >> r;
        if(s[0] == '+'){
            int x;
            cin >> x;
            Add(l,r+1,x);
        }
        else if(s[0] == '?'){
            int ans = r- l +1;
            if(l < r) ans += get(l,r).ans;
            cout << ans << endl;
        }
        else{
            Mul(l,r+1);
        }
       
    }
    return 0;
}

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