Submission #835534

#	Time	Username	Problem	Language	Result	Execution time	Memory
835534		fdnfksd	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	313 ms	37060 KiB

worst_reporter3

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll get(ll i,ll j,ll l,ll r)
{
    return max(min(j,r)-max(i,l)+1,0ll);
}
ll n,q,jump[maxN],d[maxN],nxt[maxN],m[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> d[i],jump[i]=d[i];
    for(int i=2;i<=n;i++)
    {
        ll x=jump[i-1];
        ll y=(d[i]+x-1)/x*x;
        jump[i]=y;
        m[i]=jump[i]/jump[i-1];
    }
    nxt[n]=n;
    for(int i=n-1;i>=1;i--)
    {
        nxt[i]=nxt[i+1];
        if(jump[i]!=jump[i+1]) nxt[i]=i;
    }
    for(int i=1;i<=q;i++)
    {
        ll l,r,t;
        cin >> t >> l >> r;
        ll luot=t/d[1];
        ll vd=luot*d[1]-1;
        ll ans=0;
        if(vd>=l&&vd<=r) ans=1;
        ll cur=2;
        while(cur<=n)
        {
            ll x=jump[cur];
            luot/=m[cur];
            ll cc=luot*jump[cur];
            ans+=get(l,r,cc-nxt[cur],cc-cur);
            cur=nxt[cur]+1;
        }
        ans+=((t>=l)&&(t<=r));
        cout << ans << '\n';
    }

}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'void solve()':
worst_reporter3.cpp:45:16: warning: unused variable 'x' [-Wunused-variable]
   45 |             ll x=jump[cur];
      |                ^

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81