Submission #158170

#TimeUsernameProblemLanguageResultExecution timeMemory
158170fedoseevtimofeyWorst Reporter 3 (JOI18_worst_reporter3)C++14
7 / 100
310 ms6056 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int K = 37; int L[K], R[K]; const int N = 5e5 + 7; int _time[N]; const ll Inf = 1e9 + 7; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n, q; cin >> n >> q; vector <int> d(n + 1); for (int i = 1; i <= n; ++i) cin >> d[i]; d[0] = 1; ++n; int m; { vector <pair <int, int>> seg; int lst = 0; for (int i = 1; i < n; ++i) { if (d[i] > d[lst]) { seg.push_back({lst, i - 1}); lst = i; } } seg.push_back({lst, n - 1}); for (int i = 0; i < min(K, (int)seg.size()); ++i) { L[i] = seg[i].first; R[i] = seg[i].second; } m = min(K, (int)seg.size()); _time[0] = 1; for (int i = 1; i < min(K, (int)seg.size()); ++i) { int a = L[i - 1]; int b = L[i]; ll t = (ll)_time[i - 1] * ((d[b] + d[a] - 1) / d[a]); t = min(t, Inf); _time[i] = t; } } function <int(int, int)> getPos = [&] (int id, int t) { if (id == 0) return t; for (int i = 0; i < m; ++i) { if (L[i] <= id && id <= R[i]) { if (id == L[i]) { int nt = t - (t % _time[i]); return getPos(id - 1, nt) - 1; } else { return getPos(L[i], t) - (id - L[i]); } } } assert(false); }; while (q--) { int t, l, r; cin >> t >> l >> r; int ans = 0; for (int i = 0; i < m; ++i) { ll pl = getPos(L[i], t), pr = getPos(R[i], t); swap(pl, pr); pl = max(pl, (ll)l); pr = min(pr, (ll)r); ans += max(0LL, pr - pl + 1); } cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...