Submission #774834

#	Time	Username	Problem	Language	Result	Execution time	Memory
774834		anhduc2701	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	447 ms	12044 KiB

worst_reporter3

/*
#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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81