제출 #1238684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238684		shafi_root	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	12 / 100	6 ms	1856 KiB

worst_reporter3

/* _In The Name Of God_ */

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

#define maxs(a, b)			a = max(a, b)
#define mins(a, b)			a = min(a, b)
#define pb						push_back
#define F						first
#define S						second
#define lc						id << 1
#define rc						lc|1
#define mid						((l + r)/2)
#define int                     long long

typedef pair<int, int>     	pii;
typedef long long               	ll;

const ll  MOD    = 1e9  + 7; // 998244353;
const ll  INF    = 1e9  + 1;
const int MXN    = 2e5  + 5;
const int LOG    = 23;

ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }

int n, q, d[MXN];
pii dp[MXN];

void _solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }
    dp[1] = {d[1], d[1]};
    for (int i = 2; i <= n; i++) {
        if (dp[i-1].S > d[i]) {
            dp[i].F = dp[i-1].F;
            dp[i].S = dp[i-1].S;
        }
        else {
            int x = d[i] % dp[i-1].S == 0 ? d[i] : d[i] + dp[i-1].S - d[i] % dp[i-1].S;
            dp[i].S = x;
            dp[i].F = dp[i-1].F * (x / dp[i-1].S);
        }
    }
    while (q--) {
        int s, e, t;
        cin >> t >> s >> e;
        int l = 0, r = n+1;
        while (r - l > 1) {
            if (t / dp[mid].F * dp[mid].S - mid > e) l = mid;
            else r = mid;
        }
        int f = l;
        l = 0, r = n+1;
        while (r - l > 1) {
            if (t / dp[mid].F * dp[mid].S - mid >= s) l = mid;
            else r = mid;
        }
        cout << l - f + (s <= t && t <= e) << '\n';
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--) _solve();
    return 0.0;
}

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