Submission #707589

#TimeUsernameProblemLanguageResultExecution timeMemory
707589dooompyWorst Reporter 3 (JOI18_worst_reporter3)C++17
12 / 100
539 ms31132 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; ll d[500005]; ll movedist[500005]; ll period[500005]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n, q; cin >> n >> q; movedist[0] = 1; period[0] = 1; for (int i = 1; i <= n; i++) { cin >> d[i]; // how many the prev one moes if (movedist[i - 1] >= d[i]) { movedist[i] = movedist[i - 1]; period[i] = period[i - 1]; } else { ll towait = ceil((double) (d[i]) / (double) movedist[i - 1]); movedist[i] = towait * movedist[ i- 1]; period[i] = towait * period [i - 1]; } } for (int i = 1; i <= q; i++) { ll l, r, t; cin >> t >> l >> r; ll L = 0, R = n; ll ans = -1; while (L <= R) { ll mid = ( L + R) >> 1; if (-mid + (t / period[mid]) * movedist[mid] >= l) { ans = max(ans, mid); L = mid + 1; } else R = mid - 1; } if (ans == -1) { cout << "0\n"; continue; } ll ans2 = LLONG_MAX; L = 0, R = n; while (L <= R) { ll mid = ( L + R) >> 1; if (-mid + (t / period[mid]) * movedist[mid] <= r) { ans2 = min(ans2, mid); R = mid - 1; } else L = mid + 1; } if (ans2 == LLONG_MAX) { cout << "0\n"; } cout << ans - ans2 + 1 << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...