#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef long long LL;
const int NMAX = 1e5;
int N, Q, K;
vector<int> init;
class SegmentTree
{
public:
LL ans;
vector<int> mx, mn, lzy;
vector<LL> sum;
void remake(int nod)
{
sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
mx[nod] = max(mx[nod * 2], mx[nod * 2 + 1]);
mn[nod] = min(mn[nod * 2], mn[nod * 2 + 1]);
}
void lazy(int nod, int st, int dr)
{
if(lzy[nod] == -1) return;
int mij = st + (dr - st) / 2;
int val = lzy[nod];
lzy[nod * 2] = lzy[nod * 2 + 1] = val;
sum[nod * 2] = 1LL * (mij - st + 1) * val;
mx[nod * 2] = mn[nod * 2] = val;
sum[nod * 2 + 1] = 1LL * (dr - mij) * val;
mx[nod * 2 + 1] = mn[nod * 2 + 1] = val;
lzy[nod] = -1;
}
void B(int nod, int st, int dr)
{
lzy[nod] = -1;
if(st == dr)
{
sum[nod] = mn[nod] = mx[nod] = init[st];
return;
}
int mij = st + (dr - st) / 2;
B(nod * 2, st, mij);
B(nod * 2 + 1, mij + 1, dr);
remake(nod);
}
void U(int nod, int st, int dr, int pos, int val)
{
if(st == dr)
{
sum[nod] = mx[nod] = mn[nod] = val;
return;
}
lazy(nod, st, dr);
int mij = st + (dr - st) / 2;
if(pos <= mij) U(nod * 2, st, mij, pos, val);
else U(nod * 2 + 1, mij + 1, dr, pos, val);
remake(nod);
}
void U(int nod, int st, int dr, int sti, int dri, int val)
{
if(sti <= st && dr <= dri)
{
if(mn[nod] / val == mx[nod] / val)
{
mn[nod] = mx[nod] = mn[nod] / val;
sum[nod] = 1LL * (dr - st + 1) * mn[nod];
lzy[nod] = mn[nod];
return;
}
lazy(nod, st, dr);
int mij = st + (dr - st) / 2;
U(nod * 2, st, mij, sti, dri, val);
U(nod * 2 + 1, mij + 1, dr, sti, dri, val);
remake(nod);
return;
}
lazy(nod, st, dr);
int mij = st + (dr - st) / 2;
if(sti <= mij) U(nod * 2, st, mij, sti, dri, val);
if(mij < dri) U(nod * 2 + 1, mij + 1, dr, sti, dri, val);
remake(nod);
}
void Q(int nod, int st, int dr, int sti, int dri)
{
if(sti <= st && dr <= dri)
{
ans += sum[nod];
return;
}
lazy(nod, st, dr);
int mij = st + (dr - st) / 2;
if(sti <= mij) Q(nod * 2, st, mij, sti, dri);
if(mij < dri) Q(nod * 2 + 1, mij + 1, dr, sti, dri);
}
void build()
{
sum.resize(4 * N + 2);
mx.resize(4 * N + 2);
mn.resize(4 * N + 2);
lzy.resize(4 * N + 2);
B(1, 1, N);
}
void update(int pos, int val)
{
U(1, 1, N, pos, val);
}
void divide(int st, int dr, int K)
{
if(K == 1) return;
U(1, 1, N, st, dr, K);
}
LL query(int st, int dr)
{
ans = 0;
Q(1, 1, N, st, dr);
return ans;
}
}aint;
void gen()
{
freopen("1.in", "w", stdout);
mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
int N = 10, Q = 150;
int VMAX = 100;
int K = uniform_int_distribution<int>(2, 10)(g);
printf("%d %d %d\n", N, Q, K);
for(int i = 1; i <= N; i++)
printf("%d ", uniform_int_distribution<int>(0, VMAX)(g));
printf("\n");
auto uid = uniform_int_distribution<int>(1, N);
for(int i = 1; i <= Q; i++)
{
int op = g() % 3 + 1;
if(op == 1)
{
int pos = uid(g);
printf("%d %d %d\n", op, pos, uniform_int_distribution<int>(0, VMAX)(g));
}
else
{
int st = uid(g), dr = uid(g);
if(st > dr) swap(st, dr);
printf("%d %d %d\n", op, st, dr);
}
}
exit(0);
}
int main()
{
//gen();
#ifdef FILE_IO
freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
#endif
scanf("%d%d%d", &N, &Q, &K);
init.resize(N + 2);
for(int i = 1; i <= N; i++) scanf("%d", &init[i]);
aint.build();
for(int q = 1; q <= Q; q++)
{
int op;
scanf("%d", &op);
if(op == 1)
{
int pos, val;
scanf("%d%d", &pos, &val);
aint.update(pos, val);
// init[pos] = val;
}
else if(op == 2)
{
int st, dr;
scanf("%d%d", &st, &dr);
aint.divide(st, dr, K);
// for(int i = st; i <= dr; i++) init[i] /= K;
}
else if(op == 3)
{
int st, dr;
scanf("%d%d", &st, &dr);
LL ans = aint.query(st, dr);
printf("%lld\n", ans);
// for(int i = st; i <= dr; i++) ans -= init[i];
// if(ans != 0)
// {
// cerr << "Assertion failed!" << '\n';
// ans++;
// ans--;
// }
}
}
return 0;
}
Compilation message
sterilizing.cpp: In function 'void gen()':
sterilizing.cpp:155:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("1.in", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:193:10: 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:195:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= N; i++) scanf("%d", &init[i]);
~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:200:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &op);
~~~~~^~~~~~~~~~~
sterilizing.cpp:204:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &pos, &val);
~~~~~^~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:212:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &st, &dr);
~~~~~^~~~~~~~~~~~~~~~~~
sterilizing.cpp:220:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &st, &dr);
~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
504 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
8 ms |
760 KB |
Output is correct |
6 |
Correct |
7 ms |
632 KB |
Output is correct |
7 |
Correct |
7 ms |
628 KB |
Output is correct |
8 |
Correct |
7 ms |
632 KB |
Output is correct |
9 |
Correct |
8 ms |
556 KB |
Output is correct |
10 |
Correct |
7 ms |
632 KB |
Output is correct |
11 |
Correct |
7 ms |
632 KB |
Output is correct |
12 |
Correct |
8 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
5148 KB |
Output is correct |
2 |
Correct |
60 ms |
3844 KB |
Output is correct |
3 |
Correct |
62 ms |
7464 KB |
Output is correct |
4 |
Correct |
77 ms |
9212 KB |
Output is correct |
5 |
Correct |
92 ms |
9336 KB |
Output is correct |
6 |
Correct |
91 ms |
9452 KB |
Output is correct |
7 |
Correct |
94 ms |
9464 KB |
Output is correct |
8 |
Correct |
92 ms |
9464 KB |
Output is correct |
9 |
Correct |
86 ms |
9436 KB |
Output is correct |
10 |
Correct |
88 ms |
9380 KB |
Output is correct |
11 |
Correct |
86 ms |
9464 KB |
Output is correct |
12 |
Correct |
87 ms |
9384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
1272 KB |
Output is correct |
2 |
Correct |
25 ms |
4344 KB |
Output is correct |
3 |
Correct |
33 ms |
4344 KB |
Output is correct |
4 |
Correct |
101 ms |
2896 KB |
Output is correct |
5 |
Correct |
157 ms |
8952 KB |
Output is correct |
6 |
Correct |
147 ms |
9080 KB |
Output is correct |
7 |
Correct |
75 ms |
9132 KB |
Output is correct |
8 |
Correct |
143 ms |
8952 KB |
Output is correct |
9 |
Correct |
119 ms |
8952 KB |
Output is correct |
10 |
Correct |
121 ms |
8952 KB |
Output is correct |
11 |
Correct |
119 ms |
9160 KB |
Output is correct |
12 |
Correct |
130 ms |
9080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
5112 KB |
Output is correct |
2 |
Correct |
198 ms |
6764 KB |
Output is correct |
3 |
Correct |
229 ms |
5460 KB |
Output is correct |
4 |
Correct |
234 ms |
4984 KB |
Output is correct |
5 |
Correct |
304 ms |
11384 KB |
Output is correct |
6 |
Correct |
336 ms |
11384 KB |
Output is correct |
7 |
Correct |
276 ms |
11384 KB |
Output is correct |
8 |
Correct |
410 ms |
11384 KB |
Output is correct |
9 |
Correct |
352 ms |
11228 KB |
Output is correct |
10 |
Correct |
402 ms |
11256 KB |
Output is correct |
11 |
Correct |
294 ms |
11128 KB |
Output is correct |
12 |
Correct |
557 ms |
11344 KB |
Output is correct |