#include<bits/stdc++.h>
using namespace std;
#define int long long
const int T = 262144;
const int NB_SEGTREE = 32;
const int INF = 1e18+42;
void upd(int nde, vector<int>& ab)
{
ab[nde] = ab[nde*2] + ab[nde*2 +1];
if(nde > 1)
upd(nde/2, ab);
}
void setValue(int pos, int value, vector<int>& ab)
{
ab[pos + T] = value;
upd((pos + T)/2, ab);
}
int query(int nde, int RB, int RE, int GB, int GE, vector<int>& ab)
{
if(RB > GE || RE < GB)
return 0;
if(RB >= GB && RE <= GE)
return ab[nde];
int mid = (RB + RE)/2;
return query(nde*2, RB, mid, GB, GE, ab) + query(nde*2 +1, mid+1, RE, GB, GE, ab);
}
signed main()
{
int N, Q, K;
scanf("%lld%lld%lld", &N, &Q, &K);
vector<vector<int > > ABs(NB_SEGTREE, vector<int>(2*T, 0));
for(int iN = 0; iN < N; iN++)
{
int value;
scanf("%lld", &value);
setValue(iN, value, ABs[0]);
}
set<pair<int, int>> debInterSet; // posi, prof;
debInterSet.insert({0, 0});
debInterSet.insert({N, 0});
for(int iQ = 0; iQ < Q; iQ++)
{
int type, Ti, Ui;
scanf("%lld%lld%lld", &type, &Ti, &Ui);
if(type == 1)
{
int id = Ti, newValue = Ui;
id--;
auto it = upper_bound(debInterSet.begin(), debInterSet.end(), pair<int, int>(id, +INF));
int finInterEx = (*(it)).first;
it--;
int debInter = (*(it)).first;
int profInter = (*(it)).second;
int newProf = 0;
if(id+1 <finInterEx)
debInterSet.insert({id+1, profInter});
if(debInter == id)
debInterSet.erase(it);
debInterSet.insert({id, newProf});
setValue(id, 0, ABs[profInter]);
setValue(id, newValue, ABs[0]);
}
else if(type == 2)
{
if(K!=1)
{
int l = Ti, r = Ui;
l--; r--;
while (l <= r)
{
auto it = upper_bound(debInterSet.begin(), debInterSet.end(), pair<int, int>(l, +INF));
int finInterEx = (*(it)).first;
it--;
int debInter = (*(it)).first;
int profInter = (*(it)).second;
int newProf = profInter+1;
if(r+1 <finInterEx)
debInterSet.insert({r+1, profInter});
if(debInter == l)
debInterSet.erase(it);
debInterSet.insert({l, newProf});
finInterEx = min(finInterEx, r+1);
if(profInter >= NB_SEGTREE-1)
{
l = finInterEx;
continue;
}
for(int pt = l; pt <finInterEx; pt++)
{
int valuePt = ABs[profInter][pt+T];
//printf("%lld %lld %lld-%lld\n", pt, valuePt/K, profInter, newProf);
setValue(pt, 0, ABs[profInter]);
setValue(pt, valuePt/K, ABs[newProf]);
}
l = finInterEx;
}
}
}
else if(type == 3)
{
int l = Ti, r = Ui;
l--; r--;
int res = 0;
for(int iAB = 0; iAB < NB_SEGTREE; iAB++)
{
res += query(1, 0, T-1, l, r, ABs[iAB]);
}
printf("%lld\n", res);
}
}
}
Compilation message
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%lld%lld%lld", &N, &Q, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%lld", &value);
| ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%lld%lld%lld", &type, &Ti, &Ui);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
267028 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5013 ms |
135872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
158 ms |
267016 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
267104 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
