Submission #1265681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265681		asemoonabi	ZIGZAG (INOI20_zigzag)	C++20	0 / 100	478 ms	77220 KiB

Main

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define loop(n) for(int i = 0 ;i < n ; i++)
#define lid id<<1
#define rid lid|1
#define mid (l+r)/2
#define el '\n' 
#define yes cout<<"Yes"<<el 
#define no cout<<"No"<<el 
const ll maxn = 2e6 + 100 ;
const ll oo = 1e17 + 100 ;
const ll mod = 1e9+7 ;
struct Data{ll ans , ptl1 , ptl2 , ptr1 , ptr2 , L , R , zrb , jm ;} ;
ll n , q , a[maxn] ;
Data node[maxn] ;
void relax(ll l , ll r , ll id){
    node[lid].L = node[lid].L*node[id].zrb + node[id].jm ;
    node[lid].R = node[lid].R*node[id].zrb + node[id].jm ;
    node[rid].L = node[rid].L*node[id].zrb + node[id].jm ;
    node[rid].R = node[rid].R*node[id].zrb + node[id].jm ;
    if(node[id].zrb == -1){
        swap(node[lid].ptl1,node[lid].ptl2) ;
        swap(node[lid].ptr1,node[lid].ptr2) ;
        swap(node[rid].ptl1,node[rid].ptl2) ;
        swap(node[rid].ptr1,node[rid].ptr2) ;
    }
    ll a = node[lid].zrb , b = node[lid].jm ;
    ll c = node[id].zrb , d = node[id].jm ;
    node[lid].zrb = c*a , node[lid].jm = c*b + d ;
    a = node[rid].zrb , b = node[rid].jm ;
    c = node[id].zrb , d = node[id].jm ;
    node[rid].zrb = c*a , node[rid].jm = c*b + d ;
    node[id].zrb = 1 , node[id].jm = 0 ;
    return ;
}
Data make_node(ll l , ll r , Data left , Data right){
    Data D ;
    D.ptl1 = left.ptl1 , D.ptl2 = left.ptl2 ;
    D.ptr1 = right.ptr1 , D.ptr2 = right.ptr2 ;
    D.ans = left.ans + right.ans ;
    if((left.R < right.L && (mid-1)%2 == 0) || (left.R > right.L && (mid-1)%2 == 1)){
        D.ans += (mid-left.ptr1)*(right.ptl1-mid+1) ;
        if(left.ptl1 == mid-1){D.ptl1 = right.ptl1;}
        if(right.ptr1 == mid){D.ptr1 = left.ptr1 ;}
    }
    if((left.R > right.L && (mid-1)%2 == 0) || (left.R < right.L && (mid-1)%2 == 1)){
        D.ans += (mid-left.ptr2)*(right.ptl2-mid+1) ;
        if(left.ptl2 == mid-1){D.ptl2 = right.ptl2;}
        if(right.ptr2 == mid){D.ptr2 = left.ptr2 ;}
    }
    D.L = left.L , D.R = right.R ;
    return D ;
}
void build(ll l , ll r , ll id){
    if(l+1 == r){
        node[id].ans = 1 ;
        node[id].ptl1 = node[id].ptl2 = node[id].ptr1 = node[id].ptr2 = l ;
        node[id].zrb = 1 , node[id].jm = 0 ;
        node[id].L = a[l] , node[id].R = a[l] ;
        return ;
    }
    build(l,mid,lid) ;
    build(mid,r,rid) ;
    node[id] = make_node(l,r,node[lid],node[rid]) ;
    node[id].zrb = 1 , node[id].jm = 0 ;
    return ;
}
void update(ll s , ll e , ll l  , ll r , ll id , ll x){
    if(e <= l || r <= s){return;}
    if(s <= l && r <= e){
        if(x == oo){
            node[id].L *= -1 , node[id].R *= -1 ;
            swap(node[id].ptl1,node[id].ptl2) ;
            swap(node[id].ptr1,node[id].ptr2) ;
            node[id].zrb *= -1 , node[id].jm *= -1 ;
        }
        else{
            node[id].L += x , node[id].R += x ;
            node[id].jm += x ;
        }
        return ;
    }
    relax(l,r,id) ;
    update(s,e,l,mid,lid,x) ;
    update(s,e,mid,r,rid,x) ;
    node[id] = make_node(l,r,node[lid],node[rid]) ;
    return ;
}
Data get(ll s , ll e , ll l , ll r  , ll id){
    Data D ;
    if(e <= l || r <= s){
        D.ans = 0 ; 
        D.ptl1 = D.ptl2 = l-1 ;
        D.ptr1 = D.ptr2 = r ;
        D.L = 0 , D.R = 0 ;
        D.zrb = 1 , D.jm = 0 ;
        return D ;
    }
    if(s <= l && r <= e){return node[id];}
    relax(l,r,id) ;
    return make_node(l,r,get(s,e,l,mid,lid),get(s,e,mid,r,rid)) ;
}
void solve(){
    cin>>n>>q ;
    for(ll i = 0 ; i < n ; i++){cin>>a[i];}
    build(0,n,1) ;
    for(ll _ = 0 ; _ < q ; _++){
        char ch ; cin>>ch ;
        ll l , r ; cin>>l>>r ; l-- ;
        if(ch == '+'){
            ll x ; cin>>x ;
            update(l,r,0,n,1,x) ;
        }
        if(ch == '*'){
            update(l,r,0,n,1,oo) ;
        }
        if(ch == '?'){
            cout<<get(l,r,0,n,1).ans<<el ;
        }
    }
    return ;
}
int main(){
    //std::ios_base::sync_with_stdio(false) , cin.tie(nullptr) ;
    ll t = 1; 
    //cin>>t ;
    while(t--){
        solve() ;
    }
}

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