oj.uz

Submission #774835

# Submission time Handle Problem Language Result Execution time Memory
774835 2023-07-06T04:00:52 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 472 ms 11228 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 450 ms 11084 KB Output is correct
2 Correct 466 ms 11076 KB Output is correct
3 Correct 433 ms 11144 KB Output is correct
4 Correct 467 ms 11116 KB Output is correct
5 Correct 472 ms 11164 KB Output is correct
6 Correct 446 ms 11080 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 450 ms 11084 KB Output is correct
2 Correct 466 ms 11076 KB Output is correct
3 Correct 433 ms 11144 KB Output is correct
4 Correct 467 ms 11116 KB Output is correct
5 Correct 472 ms 11164 KB Output is correct
6 Correct 446 ms 11080 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 245 ms 9148 KB Output is correct
14 Correct 246 ms 9080 KB Output is correct
15 Correct 234 ms 9120 KB Output is correct
16 Correct 246 ms 9188 KB Output is correct
17 Correct 310 ms 10484 KB Output is correct
18 Correct 312 ms 10572 KB Output is correct
19 Correct 323 ms 10420 KB Output is correct
20 Correct 314 ms 10620 KB Output is correct
21 Correct 316 ms 10516 KB Output is correct
22 Correct 325 ms 10496 KB Output is correct
23 Correct 318 ms 10572 KB Output is correct
24 Correct 316 ms 10512 KB Output is correct
25 Correct 458 ms 11228 KB Output is correct
26 Correct 424 ms 11172 KB Output is correct
27 Correct 356 ms 11024 KB Output is correct
28 Correct 377 ms 10808 KB Output is correct
29 Correct 346 ms 10880 KB Output is correct
30 Correct 352 ms 10940 KB Output is correct
31 Correct 348 ms 10856 KB Output is correct
32 Correct 328 ms 10592 KB Output is correct
33 Correct 0 ms 340 KB Output is correct