oj.uz

Submission #201873

# Submission time Handle Problem Language Result Execution time Memory
201873 2020-02-12T15:48:22 Z EntityIT Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 647 ms 21880 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int inf = 1e9 + 1;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, q; cin >> n >> q;
  vector<int> d(n);
  for (int i = 0; i < n; ++i) cin >> d[i];

  vector<int> f(n); f[0] = d[0];
  for (int i = 1; i < sz(f); ++i) f[i] = (int)min( (LL)inf, (LL)( (d[i] + f[i - 1] - 1) / f[i - 1]) * f[i - 1]);

  while (q--) {
    int t, l, r; cin >> t >> l >> r;

    int ans = (l <= t && t <= r);

    int L = 0, R = n;
    while (L < R) {
      int M = (L + R) >> 1;
      if (t - t % f[M] - (M + 1) <= r) R = M;
      else L = M + 1;
    }

    ans += -L;

    L = 0; R = n;
    while (L < R) {
      int M = (L + R) >> 1;
      if (t - t % f[M] - (M + 1) < l) R = M;
      else L = M + 1;
    }

    ans += L;

    cout << ans << '\n';
  }

  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 7544 KB Output is correct
2 Correct 619 ms 7548 KB Output is correct
3 Correct 620 ms 7288 KB Output is correct
4 Correct 647 ms 7288 KB Output is correct
5 Correct 611 ms 7288 KB Output is correct
6 Correct 621 ms 7356 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 7544 KB Output is correct
2 Correct 619 ms 7548 KB Output is correct
3 Correct 620 ms 7288 KB Output is correct
4 Correct 647 ms 7288 KB Output is correct
5 Correct 611 ms 7288 KB Output is correct
6 Correct 621 ms 7356 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 418 ms 14840 KB Output is correct
14 Correct 442 ms 14716 KB Output is correct
15 Correct 416 ms 19680 KB Output is correct
16 Correct 437 ms 19704 KB Output is correct
17 Correct 511 ms 7160 KB Output is correct
18 Correct 529 ms 7252 KB Output is correct
19 Correct 517 ms 7160 KB Output is correct
20 Correct 503 ms 7288 KB Output is correct
21 Correct 515 ms 7288 KB Output is correct
22 Correct 494 ms 7416 KB Output is correct
23 Correct 499 ms 7160 KB Output is correct
24 Correct 498 ms 7160 KB Output is correct
25 Correct 638 ms 21808 KB Output is correct
26 Correct 632 ms 21880 KB Output is correct
27 Correct 557 ms 7704 KB Output is correct
28 Correct 537 ms 7544 KB Output is correct
29 Correct 543 ms 7672 KB Output is correct
30 Correct 537 ms 7672 KB Output is correct
31 Correct 545 ms 7544 KB Output is correct
32 Correct 549 ms 21116 KB Output is correct
33 Correct 5 ms 376 KB Output is correct