| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1073360 |
2024-08-24T13:22:28 Z |
horiaboeriu |
Addk (eJOI21_addk) |
C++17 |
|
150 ms |
9556 KB |
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXN 100000
#define MAXK 10
long long a[4 * MAXN], v1[4 * MAXN], sp[MAXN + 1];
int vnr[4 * MAXN];//cate numere sunt in acel nod
char flag[4 * MAXN];
int v[MAXN + 1], vpoz[MAXK];
long long sum;
void lazy(int nod) {
v1[2 * nod] += v1[nod];
v1[2 * nod + 1] += v1[nod];
a[2 * nod] += v1[nod] * vnr[2 * nod];
a[2 * nod + 1] += v1[nod] * vnr[2 * nod + 1];
flag[2 * nod] = flag[2 * nod + 1] = 1;
flag[nod] = v1[nod] = 0;
}
void build(int nod, int st, int dr) {
int mid;
if (st == dr) {
a[nod] = sp[st];
vnr[nod] = 1;
} else {
mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
a[nod] = a[2 * nod] + a[2 * nod + 1];
vnr[nod] = vnr[2 * nod] + vnr[2 * nod + 1];
}
}
void update(int nod, int st, int dr, int x, int y, int val) {
int mid;
if (x <= st && y >= dr) {
a[nod] += (long long)val * vnr[nod];
v1[nod] += val;
flag[nod] = 1;
} else {
mid = (st + dr) / 2;
if (flag[nod] > 0) {
lazy(nod);
}
if (x <= mid) {
update(2 * nod, st, mid, x, y, val);
}
if (y > mid) {
update(2 * nod + 1, mid + 1, dr, x, y, val);
}
a[nod] = a[2 * nod] + a[2 * nod + 1];
}
}
void query(int nod, int st, int dr, int x, int y) {
int mid;
if (x <= st && y >= dr) {
sum += a[nod];
} else {
mid = (st + dr) / 2;
if (flag[nod] > 0) {
lazy(nod);
}
if (x <= mid) {
query(2 * nod, st, mid, x, y);
}
if (y > mid) {
query(2 * nod + 1, mid + 1, dr, x, y);
}
//a[nod] = a[2 * nod] + a[2 * nod + 1];
}
}
int readInt() {
int x;
char ch;
ch = fgetc(stdin);
while (isspace(ch)) {
ch = fgetc(stdin);
}
x = 0;
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = fgetc(stdin);
}
return x;
}
int main()
{
/*am un exemplu
l = 1 r = 7 m = 3
(1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6), (5, 6, 7)
1, 7 - apar o data
2, 6 - apar de doua ori
3, 4, 5 - apar de m ori, m = 3
sp[7] - sp[0] + sp[6] - sp[1] + sp[5] - sp[2]
= sp[5] + sp[6] + sp[7] - sp[0] - sp[1] - sp[2]
deci imi trebuie sume partiale la sume partiale
pentru ca sunt actualizari, cand un element de pe pozitia poz se schimba, toate sumele partiale de la poz pana la n se schimba
voi face un aint cu lazy ca sa stiu cat este fiecare suma partiala, se poate face si cu aib*/
int n, q, i, k, cer, j, x, st, dr, m;
long long s1, s2;
n = readInt();
k = readInt();
for (i = 1; i <= n; i++) {
v[i] = readInt();
sp[i] = sp[i - 1] + v[i];
}
build(1, 1, n);
q = readInt();
for (i = 0; i < q; i++) {
cer = readInt();
if (cer == 1) {
for (j = 0; j < k; j++) {
vpoz[j] = readInt();
}
x = v[vpoz[0]];
for (j = 1; j < k; j++) {
update(1, 1, n, vpoz[j - 1], n, v[vpoz[j]] - v[vpoz[j - 1]]);
v[vpoz[j - 1]] = v[vpoz[j]];
}
//acum il schimb pe ultimul cu primul
update(1, 1, n, vpoz[k - 1], n, x - v[vpoz[k - 1]]);
v[vpoz[k - 1]] = x;
} else {
st = readInt();
dr = readInt();
m = readInt();
if (m <= (dr - st + 2) / 2) {
//atunci st si dr apar o data, st + 1 si dr - 1 de doua ori si tot asa pana cadn cele din centru o sa apara de m ori
sum = 0;
query(1, 1, n, dr - m + 1, dr);
s1 = sum;
sum = 0;
if (st == 1) {
query(1, 1, n, st, st + m - 2);
} else {
query(1, 1, n, st - 1, st + m - 2);
}
s2 = sum;
printf("%lld\n", s1 - s2);
} else {
//cele din margini o sa apara de la fel de multe ori, dar de cele mai multe ori vor fi tot cele din centru, dar acesteea vor aparea de (dr - st + 2) - m ori
m = (dr - st + 2) - m;
sum = 0;
query(1, 1, n, dr - m + 1, dr);
s1 = sum;
sum = 0;
if (st == 1) {
query(1, 1, n, st, st + m - 2);
} else {
query(1, 1, n, st - 1, st + m - 2);
}
s2 = sum;
printf("%lld\n", s1 - s2);
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2648 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
5464 KB |
Output is correct |
| 2 |
Correct |
21 ms |
5720 KB |
Output is correct |
| 3 |
Correct |
34 ms |
6232 KB |
Output is correct |
| 4 |
Correct |
56 ms |
8532 KB |
Output is correct |
| 5 |
Correct |
77 ms |
9556 KB |
Output is correct |
| 6 |
Correct |
76 ms |
9300 KB |
Output is correct |
| 7 |
Correct |
73 ms |
9296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
6224 KB |
Output is correct |
| 2 |
Correct |
86 ms |
8928 KB |
Output is correct |
| 3 |
Correct |
150 ms |
8788 KB |
Output is correct |
| 4 |
Correct |
85 ms |
9548 KB |
Output is correct |
