Submission #1097016

#TimeUsernameProblemLanguageResultExecution timeMemory
1097016vladiliusWorst Reporter 3 (JOI18_worst_reporter3)C++17
100 / 100
253 ms25484 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin>>n>>q; vector<int> d(n + 1); for (int i = 1; i <= n; i++){ cin>>d[i]; } vector<int> k(n + 1); k[1] = d[1]; for (int i = 2; i <= n; i++){ k[i] = ceil(1.0 * d[i] / k[i - 1]) * k[i - 1]; } vector<pii> all; int i = 1; while (i <= n){ int j = i; while (j <= n && k[i] == k[j]){ j++; } all.pb({i, j - 1}); i = j; } while (q--){ int t, l, r; cin>>t>>l>>r; int out = (l <= t && t <= r), p = t - 1; for (auto [L, R]: all){ int f = (p + L) / k[L]; int l1 = max(l, f * k[L] - R), r1 = min(r, f * k[L] - L); out += max(0, (r1 - l1 + 1)); p = (f * k[L] - R) - 1; } cout<<out<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...