Submission #276926

#	Time	Username	Problem	Language	Result	Execution time	Memory
276926		DS007	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	617 ms	25520 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5 + 5;
int d[N], n, q;

int solveTestCase() {
    cin >> n >> q;
    d[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        d[i] = d[i] / d[i - 1] * d[i - 1] + (d[i] % d[i - 1] ? d[i - 1] : 0);
    }

    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;

        int low = 0, high = n, ans1 = n + 1, ans2 = n + 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int val = -mid + t / d[mid] * d[mid];
            if (-mid + t / d[mid] * d[mid] <= r)
                high = mid - 1, ans1 = mid;
            else
                low = mid + 1;
        }

        low = 0, high = n;
        while (low <= high) {
            int mid = (low + high) / 2;
            int val = -mid + t / d[mid] * d[mid];
            if (-mid + t / d[mid] * d[mid] < l)
                high = mid - 1, ans2 = mid;
            else
                low = mid + 1;
        }

        cout << ans2 - ans1 << "\n";
    }

    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'long long int solveTestCase()':
worst_reporter3.cpp:23:17: warning: unused variable 'val' [-Wunused-variable]
   23 |             int val = -mid + t / d[mid] * d[mid];
      |                 ^~~
worst_reporter3.cpp:33:17: warning: unused variable 'val' [-Wunused-variable]
   33 |             int val = -mid + t / d[mid] * d[mid];
      |                 ^~~

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