제출 #756882

#제출 시각아이디문제언어결과실행 시간메모리
756882ParsaSWorst Reporter 3 (JOI18_worst_reporter3)C++17
7 / 100
220 ms22708 KiB
// In the name of God #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define mp make_pair typedef long long ll; #define int ll const int N = 5e5 + 5; int n, q, d[N]; void solve() { cin >> n >> q; vector<pair<int, pair<int, int> > > vec; vec.pb({1, {0, 0}}); d[0] = 1; bool tmp = false; for (int i = 1; i <= n; i++) { cin >> d[i]; if (tmp) continue; if (d[i] <= vec.back().fi) { vec.back().se.fi--; } int c = (d[i] + vec.back().fi - 1) / vec.back().fi; if (d[i] > vec.back().fi && c <= 3e9 / vec.back().fi) { vec.pb({c * vec.back().fi, {-i, -i}}); } else if (d[i] > vec.back().fi) tmp = true; } assert((int)vec.size()==1); while (q--) { ll t, l, r; cin >> t >> l >> r; cout << max(min(r, t) - max(l, -n + t) + 1, 0LL) << '\n'; continue; int ans = 0; for (auto [a, b] : vec) { t /= a; t *= a; ll lt = b.fi + t, rt = b.se + t; ans += max(0LL, min(rt, r) - max(lt, l) + 1); } cout << ans << '\n'; } } int32_t main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...