oj.uz

Submission #403053

# Submission time Handle Problem Language Result Execution time Memory
403053 2021-05-12T17:23:55 Z 12tqian Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 737 ms 33144 KB 
#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }


const int N = 5e5 + 5;

ll d[N];
ll a[N]; // add distance a
ll b[N]; // every time b

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    f0r(i, n) cin >> d[i];
    a[0] = d[0];
    b[0] = d[0];
    f1r(i, 1, n) { 
        ll ba = a[i - 1];
        ll bb = b[i - 1];
        ll times = (d[i] + a[i - 1] - 1) / a[i - 1]; // times to add
        a[i] = a[i - 1] * times;
        b[i] = b[i - 1] * times;
    }
    reverse(a, a + n);
    reverse(b, b + n);
    auto get = [&](ll t, int loc) -> ll {
        ll A = a[loc];
        ll B = b[loc];
        loc = n - 1 - loc;
        ll res = -(loc + 1);
        res += (t / B) * A;
        return res;
    };
    auto num = [&](ll t, ll bnd) -> int {
        int lo = 0;
        int hi = n - 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (get(t, mid) <= bnd) lo = mid;
            else hi = mid - 1;
        }
        if (get(t, hi) <= bnd) return hi + 1;
        else if (get(t, lo) <= bnd) return lo + 1;
        return 0;
    };
    while (q--) {
        int t, l, r; cin >> t >> l >> r;
        int ans = num(t, r) - num(t, l - 1);
        if (l <= t && t <= r) ans++;
        cout << ans << '\n';
    }
    return 0;
}

/**
 * move in left to right order at all times
 * at time t, 
 * can be described as +a every b seconds
 * so you want to find the number of people in a certain range
 * from left to right in creasing order
 * 
 */

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:42:12: warning: unused variable 'ba' [-Wunused-variable]
   42 |         ll ba = a[i - 1];
      |            ^~
worst_reporter3.cpp:43:12: warning: unused variable 'bb' [-Wunused-variable]
   43 |         ll bb = b[i - 1];
      |            ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 30520 KB Output is correct
2 Correct 690 ms 30520 KB Output is correct
3 Correct 692 ms 30532 KB Output is correct
4 Correct 698 ms 30512 KB Output is correct
5 Correct 690 ms 30424 KB Output is correct
6 Correct 701 ms 30428 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 30520 KB Output is correct
2 Correct 690 ms 30520 KB Output is correct
3 Correct 692 ms 30532 KB Output is correct
4 Correct 698 ms 30512 KB Output is correct
5 Correct 690 ms 30424 KB Output is correct
6 Correct 701 ms 30428 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 388 ms 28992 KB Output is correct
14 Correct 383 ms 29580 KB Output is correct
15 Correct 376 ms 28272 KB Output is correct
16 Correct 380 ms 28900 KB Output is correct
17 Correct 500 ms 33144 KB Output is correct
18 Correct 495 ms 33068 KB Output is correct
19 Correct 492 ms 33032 KB Output is correct
20 Correct 488 ms 33092 KB Output is correct
21 Correct 494 ms 33060 KB Output is correct
22 Correct 489 ms 33092 KB Output is correct
23 Correct 491 ms 32940 KB Output is correct
24 Correct 525 ms 33092 KB Output is correct
25 Correct 699 ms 30496 KB Output is correct
26 Correct 737 ms 30464 KB Output is correct
27 Correct 555 ms 32652 KB Output is correct
28 Correct 532 ms 32964 KB Output is correct
29 Correct 536 ms 32580 KB Output is correct
30 Correct 565 ms 32608 KB Output is correct
31 Correct 570 ms 32860 KB Output is correct
32 Correct 576 ms 29268 KB Output is correct
33 Correct 1 ms 332 KB Output is correct