#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 5e5 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 7, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, q;
int a[nmax], d[nmax], L[nmax], R[nmax];
int r[nmax];
int get(int u){
return r[u] ? r[u] = get(r[u]) : u;
}
void Union(int u, int v){
int x = get(u);
int y = get(v);
if(x != y){
r[x] = y;
L[y] = min(L[x], L[y]);
R[y] = max(R[x], R[y]);
}
}
int b[nmax], c[nmax];
struct node{
int t, l, r;
}Q[nmax];
vector<int> nen;
ll calc(int t, int m){
int cur = 1, i = n, kq = 0;
bool ok = (t <= m);
t /= d[n];
int base = 3;
while(1){
int tx = get(i);
int l =L[tx], r = R[tx];
while(l <= r){
int mid = r + l >> 1;
if(a[mid] + (t * (b[mid] - a[mid])) <= m){
l = mid + 1;
kq = max(kq, mid);
}
else r= mid - 1;
}
// cout << a[n - 1] + (t * (b[n - 1] - a[n - 1])) << ' ';
// cout << c[L[tx]] << ' ';
i = L[tx] - 1;
if(i == 0) break;
t /= c[L[tx]];
if(!t) break;
}
int l = 1, r = i;
while(l <= r){
int mid = r+ l >> 1;
if(a[mid] <= m){
l = mid + 1;
kq = max(kq, mid);
}
else r = mid -1;
}
return kq + ok;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> q;
for(int i = 1; i <= n; ++i)cin >> d[n - i + 1], a[n - i + 1] = -i;
for(int i = 1; i <= n; ++i) L[i] = R[i] = i;
b[n] = a[n] + d[n];
for(int i = n - 1; i >= 1; --i){
if(a[i] + d[i] < b[i + 1]){
b[i] = b[i + 1] - 1;
Union(i, i + 1);
// cout << i << ' ';
}
else {
int x = b[i + 1] - a[i + 1];
int l = 2, r = 1e9, kq = -1;
while(l <= r){
int mid = r + l >> 1;
if(a[i] + d[i] < a[i + 1] + (x * mid)){
r = mid - 1;
kq = mid;
}
else l = mid + 1;
}
c[i + 1] = kq;
b[i] = a[i + 1] + (x * kq) - 1;
}
}
// cout << b[2] - a[2] << endl;
// for(int i = 1; i <= n; ++i) cout << get(i) << ' ';
// cout << c[3] << ' ' << c[1];
// calc(100, 100);
// calc(8, 5);
for(int e = 1,t,l,r; e <= q; ++e){
cin >> t >> l >> r;
cout << calc(t, r) - calc(t, l - 1)<< endl;
}
}
/*
3 1
2 3 3
8 3 5
*/
Compilation message
worst_reporter3.cpp: In function 'long long int calc(long long int, long long int)':
worst_reporter3.cpp:47:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = r + l >> 1;
| ~~^~~
worst_reporter3.cpp:63:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid = r+ l >> 1;
| ~^~~
worst_reporter3.cpp:39:9: warning: unused variable 'cur' [-Wunused-variable]
39 | int cur = 1, i = n, kq = 0;
| ^~~
worst_reporter3.cpp:42:9: warning: unused variable 'base' [-Wunused-variable]
42 | int base = 3;
| ^~~~
worst_reporter3.cpp: At global scope:
worst_reporter3.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
73 | main(){
| ^~~~
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:92:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = r + l >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
349 ms |
42324 KB |
Output is correct |
| 2 |
Correct |
332 ms |
42324 KB |
Output is correct |
| 3 |
Correct |
345 ms |
42324 KB |
Output is correct |
| 4 |
Correct |
341 ms |
42216 KB |
Output is correct |
| 5 |
Correct |
355 ms |
42232 KB |
Output is correct |
| 6 |
Correct |
381 ms |
42404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
349 ms |
42324 KB |
Output is correct |
| 2 |
Correct |
332 ms |
42324 KB |
Output is correct |
| 3 |
Correct |
345 ms |
42324 KB |
Output is correct |
| 4 |
Correct |
341 ms |
42216 KB |
Output is correct |
| 5 |
Correct |
355 ms |
42232 KB |
Output is correct |
| 6 |
Correct |
381 ms |
42404 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
480 KB |
Output is correct |
| 13 |
Correct |
176 ms |
40816 KB |
Output is correct |
| 14 |
Correct |
174 ms |
41300 KB |
Output is correct |
| 15 |
Correct |
178 ms |
40156 KB |
Output is correct |
| 16 |
Correct |
195 ms |
40692 KB |
Output is correct |
| 17 |
Correct |
517 ms |
44908 KB |
Output is correct |
| 18 |
Correct |
502 ms |
44884 KB |
Output is correct |
| 19 |
Correct |
527 ms |
45016 KB |
Output is correct |
| 20 |
Correct |
515 ms |
44884 KB |
Output is correct |
| 21 |
Correct |
567 ms |
44884 KB |
Output is correct |
| 22 |
Correct |
534 ms |
44848 KB |
Output is correct |
| 23 |
Correct |
554 ms |
44896 KB |
Output is correct |
| 24 |
Correct |
511 ms |
44944 KB |
Output is correct |
| 25 |
Correct |
386 ms |
42320 KB |
Output is correct |
| 26 |
Correct |
363 ms |
42236 KB |
Output is correct |
| 27 |
Correct |
582 ms |
44360 KB |
Output is correct |
| 28 |
Correct |
630 ms |
44868 KB |
Output is correct |
| 29 |
Correct |
606 ms |
44304 KB |
Output is correct |
| 30 |
Correct |
663 ms |
44372 KB |
Output is correct |
| 31 |
Correct |
643 ms |
44736 KB |
Output is correct |
| 32 |
Correct |
280 ms |
40788 KB |
Output is correct |
| 33 |
Correct |
0 ms |
344 KB |
Output is correct |
