This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct segS
{
long long sum, maxi;
};
long long n,k,q;
vector<segS> seg;
void upd(int i, int st, int dr, int p, long long val)
{
if(st == dr)
{
seg[p].sum = seg[p].maxi = val;
return;
}
int mij = (st+dr)/2;
if(i <= mij)
upd(i, st, mij, 2*p, val);
else
upd(i, mij+1, dr, 2*p+1, val);
seg[p].sum = seg[2*p].sum + seg[2*p+1].sum;
seg[p].maxi = max(seg[2*p].maxi, seg[2*p+1].maxi);
}
void imp(int stt, int drt, int st, int dr, int p)
{
if(st == dr)
{
seg[p].sum /= k;
seg[p].maxi /= k;
return;
}
int mij = (st+dr)/2;
if(stt <= st && dr <= drt)
{
if(seg[2*p].maxi > 0)
imp(stt, drt, st, mij, 2*p);
if(seg[2*p+1].maxi > 0)
imp(stt, drt, mij+1, dr, 2*p+1);
}
else
{
if(drt <= mij)
imp(stt, drt, st, mij, 2*p);
else if(stt > mij)
imp(stt, drt, mij+1, dr, 2*p+1);
else
{
imp(stt, mij, st, mij, 2*p);
imp(mij+1, drt, mij+1, dr, 2*p+1);
}
}
seg[p].sum = seg[2*p].sum + seg[2*p+1].sum;
seg[p].maxi = max(seg[2*p].maxi, seg[2*p+1].maxi);
}
long long query(int stt, int drt, int st, int dr, int p)
{
if(stt == st && drt == dr)
return seg[p].sum;
int mij = (st+dr)/2;
if(drt <= mij)
return query(stt, drt, st, mij, 2*p);
else if(stt > mij)
return query(stt, drt, mij+1, dr, 2*p+1);
else
return query(stt, mij, st, mij, 2*p) + query(mij+1, drt, mij+1, dr, 2*p+1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q>>k;
seg.resize(4*n+4);
for(int i=1;i<=n;i++)
{
long long x;
cin>>x;
upd(i, 1, n, 1, x);
}
while(q)
{
q--;
int tip;
cin>>tip;
if(tip == 1)
{
long long i, val;
cin>>i>>val;
upd(i, 1, n, 1, val);
}
if(tip == 2)
{
int l, r;
cin>>l>>r;
imp(l, r, 1, n, 1);
}
if(tip == 3)
{
int l, r;
cin>>l>>r;
cout<<query(l, r, 1, n, 1)<<'\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |