#include <cstdio>
#include <algorithm>
#include <vector>
#define F first
#define S second
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> jmp;
typedef pair<ii, ii> q;
struct Fenwick {
vector<int> ft;
Fenwick(int N) {
for (int i = 0; i <= N; ++i) ft.push_back(0);
}
void update(int i, int dv) {
for (; i <= ft.size(); i += i & -i) ft[i] += dv;
}
};
int main() {
int N, Q;
scanf("%d %d", &N, &Q);
int D[N], T, L, R, ans[Q];
q queries[Q];
for (int i = 0; i < N; ++i) scanf("%d", &D[i]);
for (int i = 0; i < Q; ++i) {
scanf("%d %d %d", &T, &L, &R);
queries[i] = q(ii(T, i), ii(L, R));
}
sort(queries, queries + Q);
vector<jmp> jumps;
int j = 1, l = 0;
for (int i = 0; i < N; ++i) {
if (D[i] > j) {
jumps.push_back(jmp(j, ii(l, i)));
j = j * ((D[i] + j - 1) / j);
l = i + 1;
}
}
jumps.push_back(jmp(j, ii(l, N)));
Fenwick f(1 << 19);
for (int i = 2; i <= N + 1; ++i) f.update(i, -1);
T = 0;
for (q i: queries) {
for (jmp j: jumps) f.update(j.S.F + 1, j.F * (i.F.F / j.F - T / j.F)), f.update(j.S.S + 2, -j.F * (i.F.F / j.F - T / j.F));
int l = 1, r = 1 << 19, m, v = 0, a1;
while (l != r) {
m = (l + r) >> 1;
if (v + f.ft[m] >= i.S.F) l = m + 1, v += f.ft[m];
else r = m;
}
a1 = l;
l = 1, r = 1 << 19, v = 0;
while (l != r) {
m = (l + r) >> 1;
if (v + f.ft[m] > i.S.S) l = m + 1, v += f.ft[m];
else r = m;
}
ans[i.F.S] = a1 - l;
T = i.F.F;
}
for (int i = 0; i < Q; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message
worst_reporter3.cpp: In member function 'void Fenwick::update(int, int)':
worst_reporter3.cpp:16:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; i <= ft.size(); i += i & -i) ft[i] += dv;
~~^~~~~~~~~~~~
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:24:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; ++i) scanf("%d", &D[i]);
~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &T, &L, &R);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
654 ms |
17372 KB |
Output is correct |
2 |
Correct |
661 ms |
17248 KB |
Output is correct |
3 |
Correct |
662 ms |
17372 KB |
Output is correct |
4 |
Correct |
657 ms |
17244 KB |
Output is correct |
5 |
Correct |
689 ms |
17372 KB |
Output is correct |
6 |
Correct |
661 ms |
17244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
4720 KB |
Output is correct |
2 |
Correct |
10 ms |
4592 KB |
Output is correct |
3 |
Correct |
10 ms |
4592 KB |
Output is correct |
4 |
Correct |
10 ms |
4592 KB |
Output is correct |
5 |
Correct |
11 ms |
4592 KB |
Output is correct |
6 |
Correct |
11 ms |
4592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
654 ms |
17372 KB |
Output is correct |
2 |
Correct |
661 ms |
17248 KB |
Output is correct |
3 |
Correct |
662 ms |
17372 KB |
Output is correct |
4 |
Correct |
657 ms |
17244 KB |
Output is correct |
5 |
Correct |
689 ms |
17372 KB |
Output is correct |
6 |
Correct |
661 ms |
17244 KB |
Output is correct |
7 |
Correct |
11 ms |
4720 KB |
Output is correct |
8 |
Correct |
10 ms |
4592 KB |
Output is correct |
9 |
Correct |
10 ms |
4592 KB |
Output is correct |
10 |
Correct |
10 ms |
4592 KB |
Output is correct |
11 |
Correct |
11 ms |
4592 KB |
Output is correct |
12 |
Correct |
11 ms |
4592 KB |
Output is correct |
13 |
Correct |
665 ms |
15184 KB |
Output is correct |
14 |
Correct |
683 ms |
15324 KB |
Output is correct |
15 |
Correct |
606 ms |
15200 KB |
Output is correct |
16 |
Correct |
669 ms |
15324 KB |
Output is correct |
17 |
Correct |
1406 ms |
16636 KB |
Output is correct |
18 |
Correct |
1368 ms |
16752 KB |
Output is correct |
19 |
Correct |
1521 ms |
16732 KB |
Output is correct |
20 |
Correct |
1355 ms |
16732 KB |
Output is correct |
21 |
Correct |
1430 ms |
16732 KB |
Output is correct |
22 |
Correct |
1380 ms |
16732 KB |
Output is correct |
23 |
Correct |
1332 ms |
16764 KB |
Output is correct |
24 |
Correct |
1321 ms |
16860 KB |
Output is correct |
25 |
Correct |
662 ms |
17372 KB |
Output is correct |
26 |
Correct |
697 ms |
17372 KB |
Output is correct |
27 |
Correct |
1093 ms |
17244 KB |
Output is correct |
28 |
Correct |
1242 ms |
17152 KB |
Output is correct |
29 |
Correct |
1141 ms |
17116 KB |
Output is correct |
30 |
Correct |
1199 ms |
17116 KB |
Output is correct |
31 |
Correct |
1165 ms |
17244 KB |
Output is correct |
32 |
Correct |
582 ms |
16860 KB |
Output is correct |
33 |
Correct |
11 ms |
4592 KB |
Output is correct |