#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
ll d[511111];
int n,q;
ll period[511111];
vector<pair<ll,ii> > segments;
ll solve(ll t, ll x)
{
//check IOI-chan separately :)
ll ans = 0;
if(t<=x) ans++;
/*noob solution
for(int i=1;i<=n;i++)
{
//calculate position after t seconds
ll pos = -i + (t/period[i])*period[i];
ans+=(pos<=x);
}
*/
for(int i=0;i<segments.size();i++)
{
ll per = segments[i].fi; ll l = segments[i].se.fi; ll r = segments[i].se.se;
ll extramoves = (t/per)*per;
extramoves -= x;
//count # of [l,r] which is >= extramoves
if(l>=extramoves) ans+=(r-l+1);
else if(r>=extramoves)
{
ans += (r-extramoves+1);
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>d[i];
period[1] = d[1];
ll cur = d[1]; int pre = 1;
for(int i = 2; i <= n; i++)
{
ll ext = (d[i] + cur - 1)/cur;
period[i] = ext*cur;
if(period[i]>cur)
{
segments.pb(mp(cur, mp(pre, i - 1)));
pre = i;
}
cur = period[i];
}
segments.pb(mp(cur, mp(pre, n)));
//do stupid solution first
for(int i=0;i<q;i++)
{
ll t,l,r; cin>>t>>l>>r;
cout<<solve(t,r)-solve(t,l-1)<<'\n';
}
}
Compilation message
worst_reporter3.cpp: In function 'll solve(ll, ll)':
worst_reporter3.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<segments.size();i++)
~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
342 ms |
11256 KB |
Output is correct |
2 |
Correct |
343 ms |
11256 KB |
Output is correct |
3 |
Correct |
325 ms |
11552 KB |
Output is correct |
4 |
Correct |
324 ms |
11552 KB |
Output is correct |
5 |
Correct |
333 ms |
11552 KB |
Output is correct |
6 |
Correct |
329 ms |
11552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
11552 KB |
Output is correct |
2 |
Correct |
2 ms |
11552 KB |
Output is correct |
3 |
Correct |
2 ms |
11552 KB |
Output is correct |
4 |
Correct |
2 ms |
11552 KB |
Output is correct |
5 |
Correct |
3 ms |
11552 KB |
Output is correct |
6 |
Correct |
3 ms |
11552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
342 ms |
11256 KB |
Output is correct |
2 |
Correct |
343 ms |
11256 KB |
Output is correct |
3 |
Correct |
325 ms |
11552 KB |
Output is correct |
4 |
Correct |
324 ms |
11552 KB |
Output is correct |
5 |
Correct |
333 ms |
11552 KB |
Output is correct |
6 |
Correct |
329 ms |
11552 KB |
Output is correct |
7 |
Correct |
3 ms |
11552 KB |
Output is correct |
8 |
Correct |
2 ms |
11552 KB |
Output is correct |
9 |
Correct |
2 ms |
11552 KB |
Output is correct |
10 |
Correct |
2 ms |
11552 KB |
Output is correct |
11 |
Correct |
3 ms |
11552 KB |
Output is correct |
12 |
Correct |
3 ms |
11552 KB |
Output is correct |
13 |
Correct |
367 ms |
11552 KB |
Output is correct |
14 |
Correct |
376 ms |
11552 KB |
Output is correct |
15 |
Correct |
338 ms |
11552 KB |
Output is correct |
16 |
Correct |
372 ms |
11552 KB |
Output is correct |
17 |
Correct |
630 ms |
11552 KB |
Output is correct |
18 |
Correct |
604 ms |
11552 KB |
Output is correct |
19 |
Correct |
641 ms |
11552 KB |
Output is correct |
20 |
Correct |
619 ms |
11552 KB |
Output is correct |
21 |
Correct |
614 ms |
11552 KB |
Output is correct |
22 |
Correct |
637 ms |
11552 KB |
Output is correct |
23 |
Correct |
675 ms |
11552 KB |
Output is correct |
24 |
Correct |
849 ms |
11552 KB |
Output is correct |
25 |
Correct |
386 ms |
11552 KB |
Output is correct |
26 |
Correct |
354 ms |
11580 KB |
Output is correct |
27 |
Correct |
614 ms |
11580 KB |
Output is correct |
28 |
Correct |
675 ms |
11580 KB |
Output is correct |
29 |
Correct |
684 ms |
11580 KB |
Output is correct |
30 |
Correct |
671 ms |
11580 KB |
Output is correct |
31 |
Correct |
671 ms |
11580 KB |
Output is correct |
32 |
Correct |
390 ms |
11580 KB |
Output is correct |
33 |
Correct |
2 ms |
11580 KB |
Output is correct |