| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1073003 |
2024-08-24T08:25:09 Z |
raduv |
Addk (eJOI21_addk) |
C++14 |
|
71 ms |
4436 KB |
#include <bits/stdc++.h>
const int MAXN = 100'000;
const int MAXK = 10;
int sp[MAXN + 1];
int v[MAXN + 1];
int aint[(MAXN + 1) * 4];
int no_nums[(MAXN + 1) * 4];
int poz[MAXK];
int lazy[(MAXN + 1) * 4];
void propagate(int node){
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
aint[2 * node] += lazy[node] * no_nums[2 * node];
aint[2 * node + 1] += lazy[node] * no_nums[2 * node + 1];
lazy[node] = 0;
}
void build(int node, int st, int dr){
if(st == dr){
aint[node] = sp[st];
no_nums[node] = 1;
}
else{
int mij = (st + dr) / 2;
build(2 * node, st, mij);
build(2 * node + 1, mij + 1, dr);
aint[node] = (aint[2 * node] + aint[2 * node + 1]);
no_nums[node] = (no_nums[2 * node] + no_nums[2 * node + 1]);
}
}
void update(int node, int st, int dr, int l, int r, int val){
if(l <= st && dr <= r){
aint[node] += no_nums[node] * val;
lazy[node] += val;
}
else{
if(lazy[node] > 0)
propagate(node);
int mij = (st + dr) / 2;
if(l <= mij)
update(2 * node, st, mij, l, r, val);
if(r > mij)
update(2 * node + 1, mij + 1, dr, l, r, val);
aint[node] = (aint[2 * node] + aint[2 * node + 1]);
}
}
int query(int node, int st, int dr, int l, int r){
if(l <= st && dr <= r){
return aint[node];
}
else{
if(lazy[node] > 0)
propagate(node);
int mij = (st + dr) / 2, sum = 0;
if(l <= mij)
sum += query(2 * node, st, mij, l, r);
if(r > mij)
sum += query(2 * node + 1, mij + 1, dr, l, r);
return sum;
}
}
int main()
{
int n, k, q, i, tip, j, i1, prev, aux, l, r, m;
scanf("%d%d", &n, &k);
for( i = 1; i <= n; i++ ){
scanf("%d", &v[i]);
sp[i] = sp[i - 1] + v[i];
}
build(1, 1, n);
scanf("%d", &q);
for( i = 0; i < q; i++ ){
scanf("%d", &tip);
if(tip == 1){
for( j = 0; j < k; j++ )
scanf("%d", &poz[j]);
aux = v[poz[0]];
for( j = 1; j < k; j++ ){
update(1, 1, n, poz[j - 1], n, v[poz[j]] - v[poz[j - 1]]);
v[poz[j - 1]] = v[poz[j]];
}
update(1, 1, n, poz[k - 1], n, aux - v[poz[k - 1]]);
v[poz[k - 1]] = aux;
}
else{
scanf("%d%d%d", &l, &r, &m);
printf("%d\n", query(1, 1, n, l + m - 1, r) - query(1, 1, n, l - 1, r - m));
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:65:29: warning: unused variable 'i1' [-Wunused-variable]
65 | int n, k, q, i, tip, j, i1, prev, aux, l, r, m;
| ^~
Main.cpp:65:33: warning: unused variable 'prev' [-Wunused-variable]
65 | int n, k, q, i, tip, j, i1, prev, aux, l, r, m;
| ^~~~
Main.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:68:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d", &v[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:74:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d", &tip);
| ~~~~~^~~~~~~~~~~~
Main.cpp:77:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d", &poz[j]);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d%d%d", &l, &r, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
1880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
