Submission #563193

#TimeUsernameProblemLanguageResultExecution timeMemory
563193zaneyuSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
246 ms7744 KiB
/*input 5 10 3 1 2 8 1 3 1 2 5 2 3 5 3 2 5 2 1 4 1 3 2 3 3 5 1 2 4 2 1 2 1 1 4 3 1 5 */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; #pragma GCC optimize("unroll-loops,no-stack-protector") //order_of_key #of elements less than x // find_by_order kth element typedef long long int ll; #define ld double #define pii pair<ll,ll> #define f first #define s second #define pb push_back #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define FILL(n,x) memset(n,x,sizeof(n)) #define ALL(_a) _a.begin(),_a.end() #define sz(x) (int)x.size() const ll maxn=5e5+5; const ll maxlg=__lg(maxn)+2; const ll INF64=4e18; const int INF=0x3f3f3f3f; const ll MOD=1e9+7; const ld PI=acos(-1); const ld eps=1e-9; #define lowb(x) x&(-x) #define MNTO(x,y) x=min(x,(__typeof__(x))y) #define MXTO(x,y) x=max(x,(__typeof__(x))y) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin()) #define MP make_pair ll mult(ll a,ll b){ ll res=0LL; while(b){ if(b&1) res=(res+a)%MOD; a=(a+a)%MOD; b>>=1; } return res%MOD; } ll mypow(ll a,ll b){ ll res=1LL; while(b){ if(b&1) res=res*a%MOD; a=a*a%MOD; b>>=1; } return res; } struct node{ int mx=0; ll sum=0; }seg[4*maxn]; int arr[maxn]; node pull(node a,node b){ node c; c.mx=max(a.mx,b.mx); c.sum=a.sum+b.sum; return c; } void build(int idx,int l,int r){ if(l==r){ seg[idx].mx=seg[idx].sum=arr[l]; return; } int mid=(l+r)/2; build(idx*2,l,mid); build(idx*2+1,mid+1,r); seg[idx]=pull(seg[idx*2],seg[idx*2+1]); } void mdf(int idx,int l,int r,int p,int x){ if(r<p or l>p) return; if(l==r){ seg[idx].mx=seg[idx].sum=x; return; } int mid=(l+r)/2; mdf(idx*2,l,mid,p,x); mdf(idx*2+1,mid+1,r,p,x); seg[idx]=pull(seg[idx*2],seg[idx*2+1]); } void spray(int idx,int l,int r,int ql,int qr,int k){ if(r<ql or l>qr) return; if(seg[idx].mx==0){ return; } if(l==r){ seg[idx].mx/=k; seg[idx].sum/=k; return; } int mid=(l+r)/2; spray(idx*2,l,mid,ql,qr,k); spray(idx*2+1,mid+1,r,ql,qr,k); seg[idx]=pull(seg[idx*2],seg[idx*2+1]); } ll query(int idx,int l,int r,int ql,int qr){ if(r<ql or l>qr) return 0; if(ql<=l and r<=qr){ return seg[idx].sum; } int mid=(l+r)/2; return query(idx*2,l,mid,ql,qr)+query(idx*2+1,mid+1,r,ql,qr); } int main(){ ios::sync_with_stdio(false),cin.tie(0); int n,q; cin>>n>>q; int k; cin>>k; REP(i,n){ cin>>arr[i]; } build(1,0,n-1); REP(i,q){ int x,a,b; cin>>x>>a>>b; --a; if(x==2){ --b; if(k==1) continue; spray(1,0,n-1,a,b,k); } else if(x==1){ mdf(1,0,n-1,a,b); } else{ --b; cout<<query(1,0,n-1,a,b)<<'\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...