Submission #1182631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182631		Alish	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	147 ms	5448 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){
        Mx[ind]=sum[ind]=c[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 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 upd(int lx, int rx, ll x, int l=1, int r=n+1, int ind=0){
    if(lx>=r || rx<=l || (!Mx[ind] && x==k)) return;
    if(r-l==1){
        if(x==k) sum[ind]=Mx[ind]=sum[ind]/k;
        else sum[ind]=Mx[ind]=-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);
    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){
    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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75