//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,q;
int arr[500005];
vector<ii> v; //{speed,num}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
rep(x,0,n) cin>>arr[x];
v.push_back({1,1});
rep(x,0,n){
if (v.back().fi>=arr[x]){
v.back().se++;
}
else{
v.push_back({ceil((double)arr[x]/v.back().fi)*v.back().fi,1});
}
}
ll t,l,r;
while (q--){
cin>>t>>l>>r;
int prev=t;
int curr=0;
int ans=0;
for (auto &it:v){
int pos=-curr;
int diff=prev-pos;
pos+=diff/it.fi*it.fi;
curr+=it.se;
prev=pos-it.se;
ii range={pos-it.se+1,pos};
//cout<<range.fi<<" "<<range.se<<endl;
if (range.se<l || r<range.fi) continue;
ans+=min(r,range.se)-max(l,range.fi)+1;
}
cout<<ans<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
285 ms |
5368 KB |
Output is correct |
2 |
Correct |
278 ms |
20856 KB |
Output is correct |
3 |
Correct |
285 ms |
20728 KB |
Output is correct |
4 |
Correct |
286 ms |
20800 KB |
Output is correct |
5 |
Correct |
295 ms |
20832 KB |
Output is correct |
6 |
Correct |
296 ms |
20728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
285 ms |
5368 KB |
Output is correct |
2 |
Correct |
278 ms |
20856 KB |
Output is correct |
3 |
Correct |
285 ms |
20728 KB |
Output is correct |
4 |
Correct |
286 ms |
20800 KB |
Output is correct |
5 |
Correct |
295 ms |
20832 KB |
Output is correct |
6 |
Correct |
296 ms |
20728 KB |
Output is correct |
7 |
Correct |
6 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
6 ms |
384 KB |
Output is correct |
13 |
Correct |
316 ms |
19456 KB |
Output is correct |
14 |
Correct |
355 ms |
19960 KB |
Output is correct |
15 |
Correct |
300 ms |
18556 KB |
Output is correct |
16 |
Correct |
308 ms |
19220 KB |
Output is correct |
17 |
Correct |
422 ms |
23416 KB |
Output is correct |
18 |
Correct |
414 ms |
23288 KB |
Output is correct |
19 |
Correct |
421 ms |
23672 KB |
Output is correct |
20 |
Correct |
428 ms |
23420 KB |
Output is correct |
21 |
Correct |
410 ms |
23544 KB |
Output is correct |
22 |
Correct |
423 ms |
23548 KB |
Output is correct |
23 |
Correct |
411 ms |
23288 KB |
Output is correct |
24 |
Correct |
415 ms |
23416 KB |
Output is correct |
25 |
Correct |
325 ms |
20856 KB |
Output is correct |
26 |
Correct |
308 ms |
20856 KB |
Output is correct |
27 |
Correct |
426 ms |
22904 KB |
Output is correct |
28 |
Correct |
425 ms |
23288 KB |
Output is correct |
29 |
Correct |
444 ms |
22904 KB |
Output is correct |
30 |
Correct |
435 ms |
22956 KB |
Output is correct |
31 |
Correct |
435 ms |
23220 KB |
Output is correct |
32 |
Correct |
297 ms |
19448 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |