| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1071846 |
2024-08-23T11:49:44 Z |
horiaboeriu |
Addk (eJOI21_addk) |
C++17 |
|
48 ms |
6996 KB |
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXN 200000
#define MAXK 10
long long aibv[MAXN + 1], aibsp[MAXN + 1];
int v[MAXN + 1], vpoz[MAXK];
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;
}
void addBit(int poz, int n, long long val, long long aib[]) {
while (poz <= n) {
aib[poz] += val;
poz += (poz & (-poz));
}
}
long long bitSum(int poz, long long aib[]) {
long long s;
s = 0;
while (poz > 0) {
s += aib[poz];
poz &= (poz - 1);
}
return s;
}
long long calcspsp(int st, int dr) {//calculeaza suma partiala dintre sumele partiale de la st la dr
return bitSum(dr, aibsp) - bitSum(st - 1, aibsp);
}
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 voi face sume partiale si sume partiale la sume partiale cu aib*/
int n, q, i, k, cer, j, x, st, dr, m;
long long s;
n = readInt();
k = readInt();
s = 0;
for (i = 1; i <= n; i++) {
scanf("%d", &v[i]);
s += v[i];//suma partiala pana la i
addBit(i, n, v[i], aibv);
addBit(i, n, s, aibsp);
}
q = readInt();
for (i = 0; i < q; i++) {
cer = readInt();
if (cer == 1) {
for (j = 0; j < k; j++) {
vpoz[j] = readInt();
}
if (k > 1) {
x = v[vpoz[0]];
for (j = 1; j < k; j++) {
s = bitSum(vpoz[j - 1], aibv);
addBit(vpoz[j - 1], n, v[vpoz[j]] - v[vpoz[j - 1]], aibv);
addBit(vpoz[j - 1], n, s + v[vpoz[j]] - v[vpoz[j - 1]], aibsp);//suma partiala de pe poz vpoz[j - 1] creste cu cat am adaugat la v[vpoz[j]] - v[vpoz[j - 1]]
v[vpoz[j - 1]] = v[vpoz[j]];
}
//acum il schimb pe ultimul cu primul
s = bitSum(vpoz[k - 1], aibv);
addBit(vpoz[k - 1], n, x - v[vpoz[k - 1]], aibv);
addBit(vpoz[k - 1], n, s + x - v[vpoz[k - 1]], aibsp);
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
printf("%lld\n", calcspsp(dr - m + 1, dr) - calcspsp(st - 1, st + m - 2));
} 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;
printf("%lld\n", calcspsp(dr - m + 1, dr) - calcspsp(st - 1, st + m - 2));
}
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d", &v[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
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 |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2488 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3408 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3932 KB |
Output is correct |
| 3 |
Correct |
13 ms |
4264 KB |
Output is correct |
| 4 |
Correct |
21 ms |
5888 KB |
Output is correct |
| 5 |
Correct |
30 ms |
6996 KB |
Output is correct |
| 6 |
Correct |
32 ms |
6832 KB |
Output is correct |
| 7 |
Correct |
48 ms |
6740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
5308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
