oj.uz

Submission #674190

# Submission time Handle Problem Language Result Execution time Memory
674190 2022-12-23T12:14:44 Z HuyAT Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 550 ms 25420 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 + 2;
    while(lo <= hi)
    {
        ll mid = (lo + hi) / 2,cpm = (t / a[mid]) * a[mid] - (n - mid);
        if(cpm >= l || cpm > r)
        {
            if(cpm >= l && cpm <= r)
                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,cpm = (t / a[mid] * a[mid] - (n - mid));
        if(cpm <= r || cpm < l)
        {
            if(cpm <= r && cpm >= l)
                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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 9336 KB Output is correct
2 Correct 534 ms 22684 KB Output is correct
3 Correct 516 ms 22684 KB Output is correct
4 Correct 491 ms 22700 KB Output is correct
5 Correct 520 ms 22644 KB Output is correct
6 Correct 531 ms 22716 KB Output is correct

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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 9336 KB Output is correct
2 Correct 534 ms 22684 KB Output is correct
3 Correct 516 ms 22684 KB Output is correct
4 Correct 491 ms 22700 KB Output is correct
5 Correct 520 ms 22644 KB Output is correct
6 Correct 531 ms 22716 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 323 ms 21124 KB Output is correct
14 Correct 330 ms 21720 KB Output is correct
15 Correct 306 ms 20396 KB Output is correct
16 Correct 296 ms 20968 KB Output is correct
17 Correct 404 ms 25356 KB Output is correct
18 Correct 401 ms 25216 KB Output is correct
19 Correct 390 ms 25332 KB Output is correct
20 Correct 451 ms 25236 KB Output is correct
21 Correct 437 ms 25340 KB Output is correct
22 Correct 377 ms 25420 KB Output is correct
23 Correct 381 ms 25160 KB Output is correct
24 Correct 391 ms 25252 KB Output is correct
25 Correct 550 ms 22680 KB Output is correct
26 Correct 518 ms 22668 KB Output is correct
27 Correct 425 ms 24776 KB Output is correct
28 Correct 432 ms 25124 KB Output is correct
29 Correct 437 ms 24588 KB Output is correct
30 Correct 431 ms 24820 KB Output is correct
31 Correct 450 ms 25092 KB Output is correct
32 Correct 427 ms 21348 KB Output is correct
33 Correct 1 ms 212 KB Output is correct