Submission #674182

#	Time	Username	Problem	Language	Result	Execution time	Memory
674182		HuyAT	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	470 ms	22832 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define fp(file) freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#define newl "\n"
#define ms(a,v) memset(a,v,sizeof(a))
#define ar array
#define sz(x) ((int)x.size())
#define r1(a) (a).begin(), (a).end()
#define r2(a,start,end) a + start,a + end + 1
#define PI 3.1415926535897932384626433832795l
#define ft first
#define sd second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MaxN = 5e5;
const int MaxV = 1e7;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const ld eps = 1e-9;

mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define SHUF(r) shuffle(r, RNG);

ll a[MaxN + 10];
int n,q;
void rd()
{
    cin >> n >> q;
    for(int i = 1;i <= n;++i)
        cin >> a[i];
    reverse(a + 1,a + n + 1);
    a[++n] = 1;
}
void build()
{
    for(int i = n - 1;i >= 1;--i)
    {
        if(a[i] < a[i + 1])
            a[i] = a[i + 1];
        else a[i] = ((a[i] + a[i + 1] - 1) / a[i + 1]) * a[i + 1];
    }
}
ll bs(ll t,ll l,ll r)
{
    ll lo = 1,hi = n,ans = n + 1;
    while(lo <= hi)
    {
        ll mid = (lo + hi) / 2;
        if((t / a[mid]) * a[mid] - (n - mid) >= l)
            ans = mid,hi = mid - 1;
        else lo = mid + 1;
    }
    return ans;
}
ll bs1(ll t,ll l,ll r)
{
    ll lo = 1,hi = n,ans = n + 1;
    while(lo <= hi)
    {
        ll mid = (lo + hi) / 2;
        if((t / a[mid])  * a[mid] - (n - mid)<= r)
            ans = mid,lo = mid + 1;
        else hi = mid - 1;
    }
    return ans;
}
void query()
{
    while(q--)
    {
        ll t,l,r;
        cin >> t >> l >> r;
        cout << bs1(t,l,r) - bs(t,l,r) + 1 << newl;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    int tc;
//    cin >> tc;
//    for(int i = 1;i <= tc;++i)
//    {
//
//    }
    rd();
    build();
    query();
    return 0;
}

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