#include <stdio.h>
#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */
long long min(long long a, long long b) { return a < b ? a : b; }
long long ss[N_ * 2], qq[N_ * 2]; int n_;
void pul(int i) {
int l = i << 1, r = l | 1;
ss[i] = ss[l] + ss[r];
qq[i] = min(qq[l] + ss[r], qq[r]);
}
void build(int *aa, int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n; i++) {
ss[n_ + i] += aa[i] / 2;
if (aa[i] % 2 != 0)
ss[n_ + (i + 1) / 2]--;
}
for (i = 0; i < n_; i++)
qq[n_ + i] = min(ss[n_ + i], 0);
for (i = n_ - 1; i > 0; i--)
pul(i);
}
void update(int i, int x) {
i += n_;
qq[i] = min(ss[i] += x, 0);
while (i > 1)
pul(i >>= 1);
}
int main() {
static int aa[N];
int n, q, i, d;
long long sum;
scanf("%d%d", &n, &q);
sum = 0;
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]);
sum += aa[i];
}
build(aa, n);
while (q--) {
scanf("%d%d", &i, &d), i--;
update(i, -(aa[i] / 2));
if (aa[i] % 2 != 0)
update((i + 1) / 2, 1);
aa[i] += d, sum += d;
update(i, aa[i] / 2);
if (aa[i] % 2 != 0)
update((i + 1) / 2, -1);
printf("%lld\n", (sum + qq[1]) / 3);
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:46:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
Main.c:54:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d", &i, &d), i--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
304 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
304 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
2 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
292 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
50 ms |
1356 KB |
Output is correct |
| 4 |
Correct |
140 ms |
11880 KB |
Output is correct |
| 5 |
Correct |
120 ms |
11980 KB |
Output is correct |
| 6 |
Correct |
129 ms |
11952 KB |
Output is correct |
| 7 |
Correct |
131 ms |
11928 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
138 ms |
12140 KB |
Output is correct |
| 6 |
Correct |
143 ms |
15032 KB |
Output is correct |
| 7 |
Correct |
169 ms |
14724 KB |
Output is correct |
| 8 |
Correct |
134 ms |
15096 KB |
Output is correct |
| 9 |
Correct |
134 ms |
15192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
304 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
2 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
292 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
0 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
50 ms |
1356 KB |
Output is correct |
| 32 |
Correct |
140 ms |
11880 KB |
Output is correct |
| 33 |
Correct |
120 ms |
11980 KB |
Output is correct |
| 34 |
Correct |
129 ms |
11952 KB |
Output is correct |
| 35 |
Correct |
131 ms |
11928 KB |
Output is correct |
| 36 |
Correct |
1 ms |
340 KB |
Output is correct |
| 37 |
Correct |
1 ms |
340 KB |
Output is correct |
| 38 |
Correct |
1 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
340 KB |
Output is correct |
| 40 |
Correct |
138 ms |
12140 KB |
Output is correct |
| 41 |
Correct |
143 ms |
15032 KB |
Output is correct |
| 42 |
Correct |
169 ms |
14724 KB |
Output is correct |
| 43 |
Correct |
134 ms |
15096 KB |
Output is correct |
| 44 |
Correct |
134 ms |
15192 KB |
Output is correct |
| 45 |
Correct |
192 ms |
15668 KB |
Output is correct |
| 46 |
Correct |
143 ms |
15420 KB |
Output is correct |
| 47 |
Correct |
153 ms |
15760 KB |
Output is correct |
| 48 |
Correct |
143 ms |
11884 KB |
Output is correct |
| 49 |
Correct |
119 ms |
15180 KB |
Output is correct |
| 50 |
Correct |
129 ms |
13880 KB |
Output is correct |
| 51 |
Correct |
116 ms |
14068 KB |
Output is correct |
| 52 |
Correct |
142 ms |
16680 KB |
Output is correct |
| 53 |
Correct |
118 ms |
13288 KB |
Output is correct |
| 54 |
Correct |
138 ms |
12912 KB |
Output is correct |
