oj.uz

Submission #774834

# Submission time Handle Problem Language Result Execution time Memory
774834 2023-07-06T04:00:41 Z anhduc2701 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 447 ms 12044 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, q;
int d[maxn];
int calc[maxn];
int f(int t, int id)
{
    int tim = t / calc[id];
    int dis = calc[id] * tim;
    dis -= id;
    return dis;
}
int last(int t, int pos)
{
    int l = 1;
    int r = n;
    int ans = n + 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (f(t, mid) <= pos)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return n - ans + 1;
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            calc[1] = d[1];
        }
        else
        {
            calc[i] = ((d[i] - 1) / calc[i - 1] + 1) * calc[i - 1];
        }
    }

    for (int i = 1; i <= q; i++)
    {
        int t, l, r;
        cin >> t >> l >> r;
        cout << last(t, r) - last(t, l - 1) + (l <= t && t <= r) << "\n";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 11132 KB Output is correct
2 Correct 432 ms 11864 KB Output is correct
3 Correct 432 ms 12044 KB Output is correct
4 Correct 432 ms 11932 KB Output is correct
5 Correct 433 ms 11848 KB Output is correct
6 Correct 436 ms 11872 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 447 ms 11132 KB Output is correct
2 Correct 432 ms 11864 KB Output is correct
3 Correct 432 ms 12044 KB Output is correct
4 Correct 432 ms 11932 KB Output is correct
5 Correct 433 ms 11848 KB Output is correct
6 Correct 436 ms 11872 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 247 ms 9808 KB Output is correct
14 Correct 250 ms 9192 KB Output is correct
15 Correct 237 ms 9908 KB Output is correct
16 Correct 245 ms 9932 KB Output is correct
17 Correct 315 ms 10508 KB Output is correct
18 Correct 323 ms 10528 KB Output is correct
19 Correct 317 ms 10568 KB Output is correct
20 Correct 312 ms 10596 KB Output is correct
21 Correct 317 ms 10524 KB Output is correct
22 Correct 316 ms 10560 KB Output is correct
23 Correct 319 ms 10632 KB Output is correct
24 Correct 319 ms 10620 KB Output is correct
25 Correct 447 ms 11828 KB Output is correct
26 Correct 441 ms 11888 KB Output is correct
27 Correct 357 ms 11068 KB Output is correct
28 Correct 351 ms 10844 KB Output is correct
29 Correct 352 ms 10892 KB Output is correct
30 Correct 349 ms 10980 KB Output is correct
31 Correct 388 ms 10856 KB Output is correct
32 Correct 350 ms 11328 KB Output is correct
33 Correct 1 ms 340 KB Output is correct