Submission #1182611

#TimeUsernameProblemLanguageResultExecution timeMemory
1182611AlishSterilizing Spray (JOI15_sterilizing)C++20
10 / 100
42 ms6472 KiB
#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; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...