Submission #964062

#	Time	Username	Problem	Language	Result	Execution time	Memory
964062		12345678	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	282 ms	25404 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

#define ll long long

ll n, q, d[nx], t, l, r, st, cur;
vector<pair<ll, ll>> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    d[0]=1;
    for (int i=1; i<=n; i++)
    {
        cin>>d[i];
        d[i]=d[i-1]*((d[i]-1)/d[i-1]+1);
    }
    st=1;
    for (int i=2; i<=n+1; i++) if (d[i]!=d[i-1]) v.push_back({st, i-1}), st=i;
    //for (auto [x, y]:v) cout<<"debug "<<x<<' '<<y<<'\n';
    while (q--)
    {
        cin>>t>>l>>r;
        ll res=(l<=t&&t<=r);
        cur=t;
        for (auto [x, y]:v)
        {
            ll m=(cur-(-x)-1)/d[y];
            //cout<<"move "<<x<<' '<<y<<' '<<m*d[y]<<'\n';
            ll a=-y+m*d[y], b=-x+m*d[y];
            //cout<<"here "<<a<<' '<<b<<'\n';
            if (b<l||r<a) res+=0;
            else if (l<=a&&b<=r) res+=b-a+1;
            else if (a<=l&&r<=b) res+=r-l+1;
            else res+=min(abs(r-a)+1, abs(l-b)+1);
            cur=-y+m*d[y];
        }
        cout<<res<<'\n';
    }
}

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