Submission #774832

#TimeUsernameProblemLanguageResultExecution timeMemory
774832anhduc2701Worst Reporter 3 (JOI18_worst_reporter3)C++17
0 / 100
426 ms11176 KiB
/* #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]) / 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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...