#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
456 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
5 ms |
592 KB |
Output is correct |
6 |
Correct |
4 ms |
596 KB |
Output is correct |
7 |
Correct |
5 ms |
588 KB |
Output is correct |
8 |
Correct |
4 ms |
596 KB |
Output is correct |
9 |
Correct |
7 ms |
592 KB |
Output is correct |
10 |
Correct |
4 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
4 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5092 ms |
5104 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
1108 KB |
Output is correct |
2 |
Correct |
18 ms |
3372 KB |
Output is correct |
3 |
Correct |
24 ms |
3508 KB |
Output is correct |
4 |
Correct |
62 ms |
3008 KB |
Output is correct |
5 |
Correct |
86 ms |
8004 KB |
Output is correct |
6 |
Correct |
78 ms |
7984 KB |
Output is correct |
7 |
Execution timed out |
5067 ms |
7620 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
5188 KB |
Output is correct |
2 |
Correct |
99 ms |
5376 KB |
Output is correct |
3 |
Correct |
111 ms |
4308 KB |
Output is correct |
4 |
Correct |
113 ms |
4248 KB |
Output is correct |
5 |
Correct |
173 ms |
9304 KB |
Output is correct |
6 |
Correct |
155 ms |
9404 KB |
Output is correct |
7 |
Correct |
139 ms |
9376 KB |
Output is correct |
8 |
Correct |
200 ms |
9388 KB |
Output is correct |
9 |
Correct |
160 ms |
9108 KB |
Output is correct |
10 |
Correct |
179 ms |
9116 KB |
Output is correct |
11 |
Correct |
161 ms |
9164 KB |
Output is correct |
12 |
Correct |
234 ms |
9132 KB |
Output is correct |