#include <bits/stdc++.h>
using namespace std;
const int lim = 1e9;
const int Nmax = 5e5 + 5;
typedef long long ll;
int tmp, x, y, up, D, i, N, Q, n, F, S, cnt;
int d[Nmax], t[Nmax], start[Nmax], finish[Nmax];
int main()
{
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
cin.sync_with_stdio(false);
cin >> N >> Q;
n = 1, t[1] = 1, d[1] = 1;
bool ok = 1;
for(i=1; i<=N; ++i)
{
cin >> D;
if(!ok) continue;
up = D / d[n];
if(D % d[n]) ++up;
if((ll) up * t[n] > lim || (ll) up * d[n] > lim) ok = 0;
if(up == 1) start[n] --;
else
{
++n;
start[n] = finish[n] = -i;
t[n] = t[n-1] * up;
d[n] = d[n-1] * up;
}
}
while(Q--)
{
cin >> tmp >> x >> y;
int ans = 0;
for(i=1; i<=n; ++i)
{
cnt = tmp / t[i];
S = start[i] + cnt * d[i];
F = finish[i] + cnt * d[i];
ans += max(0, min(y, F) - max(x, S) + 1);
}
cout << ans << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1042 ms |
3460 KB |
Output is correct |
2 |
Correct |
1081 ms |
3504 KB |
Output is correct |
3 |
Correct |
1020 ms |
3672 KB |
Output is correct |
4 |
Correct |
1041 ms |
3672 KB |
Output is correct |
5 |
Correct |
994 ms |
3672 KB |
Output is correct |
6 |
Correct |
1006 ms |
3708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3708 KB |
Output is correct |
2 |
Correct |
4 ms |
3708 KB |
Output is correct |
3 |
Correct |
4 ms |
3708 KB |
Output is correct |
4 |
Correct |
5 ms |
3708 KB |
Output is correct |
5 |
Correct |
4 ms |
3708 KB |
Output is correct |
6 |
Correct |
5 ms |
3708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1042 ms |
3460 KB |
Output is correct |
2 |
Correct |
1081 ms |
3504 KB |
Output is correct |
3 |
Correct |
1020 ms |
3672 KB |
Output is correct |
4 |
Correct |
1041 ms |
3672 KB |
Output is correct |
5 |
Correct |
994 ms |
3672 KB |
Output is correct |
6 |
Correct |
1006 ms |
3708 KB |
Output is correct |
7 |
Correct |
6 ms |
3708 KB |
Output is correct |
8 |
Correct |
4 ms |
3708 KB |
Output is correct |
9 |
Correct |
4 ms |
3708 KB |
Output is correct |
10 |
Correct |
5 ms |
3708 KB |
Output is correct |
11 |
Correct |
4 ms |
3708 KB |
Output is correct |
12 |
Correct |
5 ms |
3708 KB |
Output is correct |
13 |
Correct |
1025 ms |
5416 KB |
Output is correct |
14 |
Correct |
1185 ms |
22040 KB |
Output is correct |
15 |
Correct |
1158 ms |
37268 KB |
Output is correct |
16 |
Correct |
1029 ms |
52880 KB |
Output is correct |
17 |
Correct |
1162 ms |
72912 KB |
Output is correct |
18 |
Correct |
1269 ms |
91680 KB |
Output is correct |
19 |
Correct |
1213 ms |
110200 KB |
Output is correct |
20 |
Correct |
1206 ms |
128896 KB |
Output is correct |
21 |
Correct |
1137 ms |
147584 KB |
Output is correct |
22 |
Correct |
1147 ms |
166296 KB |
Output is correct |
23 |
Correct |
1121 ms |
184796 KB |
Output is correct |
24 |
Correct |
1109 ms |
203424 KB |
Output is correct |
25 |
Correct |
1172 ms |
219472 KB |
Output is correct |
26 |
Correct |
1012 ms |
235100 KB |
Output is correct |
27 |
Correct |
1191 ms |
252488 KB |
Output is correct |
28 |
Correct |
1141 ms |
270712 KB |
Output is correct |
29 |
Correct |
1151 ms |
288424 KB |
Output is correct |
30 |
Correct |
1151 ms |
306224 KB |
Output is correct |
31 |
Correct |
1131 ms |
324128 KB |
Output is correct |
32 |
Correct |
1119 ms |
338520 KB |
Output is correct |
33 |
Correct |
3 ms |
338520 KB |
Output is correct |