#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
int n, q, k;
const int N = 1e5 + 5;
set<int> seg[4*N];
int sum[4*N];
vector<int> a(N);
int get_sum(int node, int l, int r, int i, int j)
{
if(i>r||j<l) return 0;
if(i>=l&&j<=r) return sum[node];
int mid = (i+j)/2;
return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}
void update(int node, int l, int r, int pos, int x)
{
if(l==r)
{
sum[node] = x;
return;
}
int mid = (l+r)/2;
if(pos>mid)
update(node*2+2, mid+1, r, pos, x);
else
update(node*2+1, l, mid, pos, x);
sum[node] = sum[node*2+1] + sum[node*2+2];
}
void build(int node, int l, int r)
{
if(l==r)
{
if(a[l])
seg[node].insert(l);
return;
}
for(int s = l;s<=r;s++)
if(a[s]) seg[node].insert(s);
int mid = (l+r)/2;
build(node*2+1, l, mid);
build(node*2+2, mid+1, r);
}
int build_sum(int node, int l, int r)
{
if(l==r)
{
return sum[node] = a[l];
}
int mid = (l+r)/2;
return sum[node] = build_sum(node*2+1, l, mid) + build_sum(node*2+2, mid+1, r);
}
void _erase(int node, int l, int r, int pos, int x)
{
if(pos>=l&&pos<=r)
seg[node].erase(x);
if(l==r)
return;
int mid = (l+r)/2;
if(pos>mid)
_erase(node*2+2, mid+1, r, pos, x);
else
_erase(node*2+1, l, mid, pos, x);
}
void _insert(int node, int l, int r, int pos, int x)
{
if(pos>=l&&pos<=r) seg[node].insert(x);
if(l==r)
return;
int mid = (l+r)/2;
if(pos>mid)
_insert(node*2+2, mid+1, r, pos, x);
else
_insert(node*2+1, l, mid, pos, x);
}
set<int> get_alive(int node, int l, int r, int i, int j)
{
if(i>r||j<l) {
set<int> q;
return q;
}
if(i>=l&&j<=r)
return seg[node];
int mid = (i+j)/2;
set<int> levo = get_alive(node*2+1, l, r, i, mid);
set<int> desno = get_alive(node*2+2, l, r, mid+1, j);
set<int> ans;
for(int x : levo)
ans.insert(x);
for(int x : desno)
ans.insert(x);
return ans;
}
int main()
{
ios
cin>>n>>q>>k;
for(int i = 0;i<n;i++)
cin>>a[i];
build(0, 0, n-1);
//cout<<11111<<endl;
build_sum(0, 0, n-1);
//cout<<2222<<endl;
while(q--)
{
int s, t, u;
//line
cin>>s>>t>>u;
t--;
u--;
if(s==1)
{
// a-ti tanjir na b
u++;
if(!a[t]&&u)
_insert(0, 0, n-1, t, t);
if(a[t]&&!u)
_erase(0, 0, n-1, t, t);
a[t] = u;
update(0, 0, n-1, t, u);
}
else if(s==2)
{
// sprej
set<int> qq = get_alive(0, t, u, 0, n-1);
for(int x : qq)
{
//cout<<x<<" ";
a[x] /= k;
if(!a[x])
_erase(0, 0, n-1, x, x);
update(0, 0, n-1, x, a[x]);
}
//cout<<endl;
}
else{
// ispisi sumu od l do r
//cout<<u<<" "<<t<<endl;
cout<<get_sum(0, t, u, 0, n-1)<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5077 ms |
63212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
22252 KB |
Output is correct |
| 2 |
Correct |
127 ms |
37868 KB |
Output is correct |
| 3 |
Correct |
143 ms |
38720 KB |
Output is correct |
| 4 |
Correct |
171 ms |
30316 KB |
Output is correct |
| 5 |
Correct |
409 ms |
64876 KB |
Output is correct |
| 6 |
Correct |
414 ms |
64108 KB |
Output is correct |
| 7 |
Execution timed out |
5081 ms |
66968 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
832 ms |
65900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
