Submission #47602

#	Time	Username	Problem	Language	Result	Execution time	Memory
47602		qoo2p5	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	827 ms	5672 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 5e5 + 123;

int n, q;
int d[N];

void run() {
    cin >> n >> q;
    rep(i, 1, n + 1) {
        cin >> d[i];
    }
    rep(i, 2, n + 1) {
        d[i] = (d[i] + d[i - 1] - 1) / d[i - 1] * d[i - 1];
    }
    rep(i, 0, q) {
        int t, l, r;
        cin >> t >> l >> r;
        
        int L, R;
        
        {
            int left = 0;
            int right = n + 1;
            while (right - left > 1) {
                int mid = (left + right) / 2;
                int dist = l + mid;
                int k = (dist + d[mid] - 1) / d[mid];
                if (d[mid] * k <= t) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            L = left;
        }
        
        {
            int left = 0;
            int right = (n + 1);
            while (right - left > 1) {
                int mid = (left + right) / 2;
                int dist = r + mid + 1;
                int k = (dist + d[mid] - 1) / d[mid];
                if (d[mid] * k <= t) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            R = left;
        }
        
        cout << (L - R + (l <= t && t <= r)) << "\n";
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81