Submission #399934

#TimeUsernameProblemLanguageResultExecution timeMemory
399934GioChkhaidzeWorst Reporter 3 (JOI18_worst_reporter3)C++14
100 / 100
357 ms23500 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define f first #define s second using namespace std; const int N = 5e5 + 5; int n, q, d[N]; vector < pair < int , int > > v; main () { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> d[i]; } int x = 1; for (int i = 1; i <= n; ++i) { if (!v.size() || x < d[i]) { v.pb({x * ((d[i] - 1) / x + 1), 1}); x = v.back().f; } else if (d[i] <= x) { ++v.back().s; } } int t, l, r, sum, ans, L, R; for (int i = 1; i <= q; ++i) { cin >> t >> l >> r; if (t < l) { cout << 0 << "\n"; continue; } sum = -1, ans = (l <= t && t <= r); for (int j = 0; j < v.size(); ++j) { R = t + (sum - t % v[j].f); L = R - v[j].s + 1; if (R < l) break; if (R > r) R = r; if (L < l) L = l; if (L <= R) ans += R - L + 1; sum -= v[j].s; } cout << ans << "\n"; } }

Compilation message (stderr)

worst_reporter3.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main () {
      |       ^
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j = 0; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...