oj.uz

Submission #674182

# Submission time Handle Problem Language Result Execution time Memory
674182 2022-12-23T11:44:19 Z HuyAT Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 470 ms 22832 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 470 ms 22832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 352 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 470 ms 22832 KB Output isn't correct
2 Halted 0 ms 0 KB -