#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
#define SQN (333)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
struct BUC {
ll Y[MAXN][31];
ll sum[MAXN/SQN+5][31];
int sumidx[MAXN/SQN+5];
int getIdx(int X) { return (X-1)/SQN + 1; }
int getSidx(int idx) { return (idx-1)*SQN + 1; }
int getEidx(int idx) { return idx*SQN; }
void rotY(int X, int cnt = 1) {
if(!cnt) return; if(31 < cnt) cnt = 31;
for(int i = cnt; i < 31; i++) Y[X][i-cnt] = Y[X][i];
for(int i = 31-cnt; i < 31; i++) Y[X][i] = 0;
}
void updBuc(int idx) {
const int S = getSidx(idx), E = getEidx(idx);
for(int i = S; i <= E; i++) rotY(i, sumidx[idx]);
sumidx[idx] = 0; fill(sum[idx], sum[idx]+31, 0);
for(int i = S; i <= E; i++) for(int j = 0; j < 31; j++)
sum[idx][j] += Y[i][j];
}
void update(int S, int E) {
const int Sidx = getIdx(S), Eidx = getIdx(E);
if(Sidx == Eidx) {
for(int i = S; i <= E; i++) rotY(i);
updBuc(Sidx);
} else {
for(int i = Sidx+1; i < Eidx; i++) sumidx[i]++;
for(int i = Sidx+1; i < Eidx; i++) if(30 < sumidx[i]) sumidx[i] = 30;
for(int i = getEidx(Sidx); S <= i; i--) rotY(i);
for(int i = getSidx(Eidx); i <= E; i++) rotY(i);
updBuc(Sidx); updBuc(Eidx);
}
}
void __insert(int X, int R, int K) {
for(int i = 0; i < 31; R /= K, i++) Y[X][i] = R;
}
void insert(int X, int R, int K) {
updBuc(getIdx(X));
__insert(X, R, K);
updBuc(getIdx(X));
}
void __updateall(int N) {
for(int i = getIdx(N); i; i--) updBuc(i);
}
ll getSum(int S, int E) {
const int Sidx = getIdx(S), Eidx = getIdx(E);
ll ret = 0;
if(Sidx == Eidx) {
updBuc(Sidx);
for(int i = S; i <= E; i++) ret += Y[i][0];
} else {
updBuc(Sidx); updBuc(Eidx);
for(int i = Sidx+1; i < Eidx; i++) ret += sum[i][sumidx[i]];
for(int i = getEidx(Sidx); S <= i; i--) ret += Y[i][0];
for(int i = getSidx(Eidx); i <= E; i++) ret += Y[i][0];
}
return ret;
}
};
struct BIT {
ll d[MAXN], v[MAXN];
void _upd(int i, ll r) { for(; i < MAXN; i += rb(i)) d[i] += r; }
void upd(int i, int r) { _upd(i, (ll)r-v[i]); v[i] = r; }
ll get(int i) {
ll r = 0; for(; i; i -= rb(i)) r += d[i];
return r;
}
ll get(int s, int e) { return get(e) - get(s-1); }
};
BUC BT;
BIT ST;
int N, Q, K;
int main() {
scanf("%d%d%d", &N, &Q, &K);
for(int i = 1, c; i <= N; i++) {
scanf("%d", &c);
if(1 == K) ST.upd(i, c);
else BT.__insert(i, c, K);
}
if(1 != K) BT.__updateall(N);
for(int type, a, b; Q--;) {
scanf("%d%d%d", &type, &a, &b);
if(1 == type) {
if(1 == K) ST.upd(a, b);
else BT.insert(a, b, K);
} else if(2 == type) {
if(1 != K) BT.update(a, b);
} else {
printf("%lld\n", (1 == K) ? ST.get(a, b) : BT.getSum(a, b));
}
}
return 0;
}
Compilation message
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:110:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &Q, &K);
^
sterilizing.cpp:112:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c);
^
sterilizing.cpp:118:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &type, &a, &b);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
27880 KB |
Output is correct |
| 2 |
Correct |
0 ms |
27880 KB |
Output is correct |
| 3 |
Correct |
9 ms |
27880 KB |
Output is correct |
| 4 |
Correct |
63 ms |
27880 KB |
Output is correct |
| 5 |
Correct |
96 ms |
27880 KB |
Output is correct |
| 6 |
Correct |
79 ms |
27880 KB |
Output is correct |
| 7 |
Correct |
109 ms |
27880 KB |
Output is correct |
| 8 |
Correct |
79 ms |
27880 KB |
Output is correct |
| 9 |
Correct |
89 ms |
27880 KB |
Output is correct |
| 10 |
Correct |
76 ms |
27880 KB |
Output is correct |
| 11 |
Correct |
79 ms |
27880 KB |
Output is correct |
| 12 |
Correct |
83 ms |
27880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
27880 KB |
Output is correct |
| 2 |
Correct |
59 ms |
27880 KB |
Output is correct |
| 3 |
Correct |
39 ms |
27880 KB |
Output is correct |
| 4 |
Correct |
59 ms |
27880 KB |
Output is correct |
| 5 |
Correct |
99 ms |
27880 KB |
Output is correct |
| 6 |
Correct |
83 ms |
27880 KB |
Output is correct |
| 7 |
Correct |
86 ms |
27880 KB |
Output is correct |
| 8 |
Correct |
79 ms |
27880 KB |
Output is correct |
| 9 |
Correct |
83 ms |
27880 KB |
Output is correct |
| 10 |
Correct |
73 ms |
27880 KB |
Output is correct |
| 11 |
Correct |
89 ms |
27880 KB |
Output is correct |
| 12 |
Correct |
63 ms |
27880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1319 ms |
27880 KB |
Output is correct |
| 2 |
Correct |
723 ms |
27880 KB |
Output is correct |
| 3 |
Correct |
1259 ms |
27880 KB |
Output is correct |
| 4 |
Correct |
3586 ms |
27880 KB |
Output is correct |
| 5 |
Execution timed out |
5000 ms |
27880 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2853 ms |
27880 KB |
Output is correct |
| 2 |
Correct |
3253 ms |
27880 KB |
Output is correct |
| 3 |
Correct |
2259 ms |
27880 KB |
Output is correct |
| 4 |
Correct |
4143 ms |
27880 KB |
Output is correct |
| 5 |
Execution timed out |
5000 ms |
27880 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
