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;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
int lazy[402000], a[100009], n, m, K, f[402000], imax[402000];
void init(int k, int l, int r)
{
if(l == r)
{
f[k] = a[l];
imax[k] = a[l];
return ;
}
int mid = (l + r) / 2;
init(k * 2, l, mid);
init(k * 2 + 1, mid + 1, r);
f[k] = f[k * 2] + f[k * 2 + 1];
imax[k] = max(imax[k * 2], imax[k * 2 + 1]);
}
void upd(int k, int l, int r, int L, int R)
{
if(r < L || R < l || r < l)
return ;
if(l == r)
{
f[k] = f[k] / K;
imax[k] = f[k];
return;
}
int mid = (l + r) / 2;
if(imax[k * 2] > 0)
upd(k * 2, l, mid, L, R);
if(imax[k * 2 + 1] > 0)
upd(k * 2 + 1, mid + 1, r, L, R);
f[k] = f[k * 2] + f[k * 2 + 1];
imax[k] = max(imax[k * 2], imax[k * 2 + 1]);
}
void updd(int k, int l, int r, int pos, int val)
{
if(r < pos || l > pos)
return;
if(l == pos && r == pos)
{
f[k] = val;
imax[k] = f[k];
return;
}
int mid = (l + r) / 2;
updd(k * 2, l, mid, pos, val);
updd(k * 2 + 1, mid + 1, r, pos, val);
f[k] = f[k * 2] + f[k * 2 + 1];
imax[k] = max(imax[k * 2], imax[k * 2 + 1]);
}
int getsum(int k, int l, int r, int L, int R)
{
if(r < L || R < l || r < l)
return 0;
if(L <= l && r <= R)
return f[k];
int mid = (l + r) / 2;
return getsum(k * 2, l, mid, L, R) + getsum(k * 2 + 1, mid + 1, r, L, R);
}
signed main()
{
cin >> n >> m >> K;
for(int i = 1; i <= n; i++)
cin >> a[i];
init(1, 1, n);
while(m --)
{
int t, l, r;
cin >> t >> l >> r;
if(t == 1)
updd(1, 1, n, l, r);
else if(t == 2)
upd(1, 1, n, l, r);
else
cout << getsum(1, 1, n, l, r) << endl;
}
}
# | 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... |