Submission #1182618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182618		Alish	Sterilizing Spray (JOI15_sterilizing)	C++20	10 / 100	42 ms	6472 KiB

sterilizing

#include<bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int N = 1e5+23;

int Mn[4*N], Mx[4*N], lpz[4*N];
ll sum[4*N];
int c[N];
int n, k, q;

void build(int l=1, int r=n+1, int ind=0){
    lpz[ind]=-1;
    if(r-l==1){
        Mn[ind]=Mx[ind]=sum[ind]=c[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
    Mn[ind]=min(Mn[2*ind+1], Mn[2*ind+2]); Mx[ind]=max(Mx[2*ind+1], Mx[2*ind+2]); sum[ind]=sum[2*ind+1]+sum[2*ind+2];
}

void Shift(int l, int r, int ind){
    if(r-l==1) return;
    if(lpz[ind]==-1) return;
    lpz[2*ind+1]=lpz[2*ind+2]=Mn[2*ind+1]=Mn[2*ind+2]=Mx[2*ind+1]=Mn[2*ind+2]=lpz[ind];
    int mid=(r+l)>>1;
    sum[2*ind+1]=1ll*(mid-l)*lpz[ind];
    sum[2*ind+2]=1ll*(r-mid)*lpz[ind];
    lpz[ind]=-1;
}

void upd(int lx, int rx, ll x, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return;
    if(lx<=l && rx>=r && Mx[ind]==Mn[ind]){
        if(x<=0) sum[ind]=Mx[ind]=Mn[ind]=-x;
        else{
            ll temp=Mx[ind];
            Mx[ind]=Mn[ind]=temp/x;
            sum[ind]=(temp/x)*(r-l);
            lpz[ind]=temp/x;
        }
        return;
    }
    int mid=(r+l)>>1;
    upd(lx, rx, x, l, mid, 2*ind+1); upd(lx, rx, x, mid, r, 2*ind+2);
    Mn[ind]=min(Mn[2*ind+1], Mn[2*ind+2]); Mx[ind]=max(Mx[2*ind+1], Mx[2*ind+2]); sum[ind]=sum[2*ind+1]+sum[2*ind+2];
}

ll get(int lx, int rx, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return 0;
    if(lx<=l && rx>=r) return sum[ind];
    int mid=(r+l)>>1;
    return get(lx, rx, l, mid, 2*ind+1)+get(lx, rx, mid, r, 2*ind+2);
}

int main()
{
    fast_io
    cin>>n>>q>>k;
    for (int i=1; i<=n; i++) cin>>c[i];
    build();

    while(q--){
        int t; cin>>t;
        if(t==1){
            int i, x; cin>>i>>x;
            upd(i, i+1, -x);
        }
        else if(t==2){
            int l, r; cin>>l>>r; r++;
            if(k!=1) upd(l, r, k);
        }
        else{
            int l, r; cin>>l>>r; r++;
            cout<<get(l, r)<<endl;
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75