Submission #1189290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189290		c0det1ger	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	343 ms	11264 KiB

worst_reporter3

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
using namespace std;

#define int long long
#define double long double
#define codetiger_orz cin.tie(0);cin.sync_with_stdio(0);

signed main() {
    codetiger_orz
    
    int n, q;
    cin >> n >> q;
    vector<int> d(n + 1), cyc(n + 1);
    cyc[0] = d[0] = 1;
    for (int i = 1; i <= n; i++){
        cin >> d[i];
        cyc[i] = (d[i] + cyc[i - 1] - 1) / cyc[i - 1] * cyc[i - 1];
    }
    while (q--){
        int t, l, r;
        cin >> t >> l >> r;
        int ll = 0, rr = n;
        while (ll < rr){
            int mid = (ll + rr + 1) / 2;
            if (-1 * mid + t / cyc[mid] * cyc[mid] >= l){
                ll = mid;
            }
            else{
                rr = mid - 1;
            }
        }
        int L = ll;
        ll = 0; rr = n;
        while (ll < rr){
            int mid = (ll + rr) / 2;
            if (-1 * mid + t / cyc[mid] * cyc[mid] > r){
                ll = mid + 1;
            }
            else{
                rr = mid;
            }
        }
        if (t / cyc[0] * cyc[0] < l){
            L--;
        }
        if (-1 * n + t / cyc[n] * cyc[n] > r){
            ll++;
        }
        cout << L - ll + 1 << "\n";
    }
}

/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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