oj.uz

Submission #528810

# Submission time Handle Problem Language Result Execution time Memory
528810 2022-02-21T13:42:24 Z Lobo Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 514 ms 25188 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 510000

int n, q, d[maxn];

void solve() {
    cin >> n >> q;

    for(int i = 1; i <= n; i++) {
        cin >> d[i];
    }

    for(int i = 2; i <= n; i++) {
        d[i] = d[i-1]*((d[i]+d[i-1]-1)/d[i-1]);
    }

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

        int l1 = 1;
        int r1 = n;
        int ans1 = inf;
        //pos[i] >= pos[i-1]
        //encontrar o menor i que tem pos <= r
        while(l1 <= r1) {
            int mid = (l1+r1)/2;

            int pos = -mid+(t/d[mid])*d[mid];

            if(pos <= r) {
                ans1 = mid;
                r1 = mid-1;
            }
            else {
                l1 = mid+1;
            }
        }

        int l2 = 1;
        int r2 = n;
        int ans2 = 0;
        //pos[i] >= pos[i-1]
        //encontrar o maior i que tem pos[i] >= l
        while(l2 <= r2) {
            int mid = (l2+r2)/2;

            int pos = -mid+(t/d[mid])*d[mid];

            if(pos >= l) {
                ans2 = mid;
                l2 = mid+1;
            }
            else {
                r2 = mid-1;
            }
        }

        int ans = max(0LL,ans2-ans1+1);
        if(l <= t && t <= r) ans++;

        cout << ans << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 7108 KB Output is correct
2 Correct 492 ms 22616 KB Output is correct
3 Correct 503 ms 22600 KB Output is correct
4 Correct 513 ms 22788 KB Output is correct
5 Correct 514 ms 22876 KB Output is correct
6 Correct 505 ms 22724 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 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 482 ms 7108 KB Output is correct
2 Correct 492 ms 22616 KB Output is correct
3 Correct 503 ms 22600 KB Output is correct
4 Correct 513 ms 22788 KB Output is correct
5 Correct 514 ms 22876 KB Output is correct
6 Correct 505 ms 22724 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 305 ms 21076 KB Output is correct
14 Correct 304 ms 21704 KB Output is correct
15 Correct 297 ms 20332 KB Output is correct
16 Correct 308 ms 20924 KB Output is correct
17 Correct 387 ms 25188 KB Output is correct
18 Correct 377 ms 25064 KB Output is correct
19 Correct 377 ms 25076 KB Output is correct
20 Correct 447 ms 25184 KB Output is correct
21 Correct 378 ms 25056 KB Output is correct
22 Correct 389 ms 25112 KB Output is correct
23 Correct 366 ms 24976 KB Output is correct
24 Correct 371 ms 25176 KB Output is correct
25 Correct 493 ms 22640 KB Output is correct
26 Correct 510 ms 22680 KB Output is correct
27 Correct 434 ms 24708 KB Output is correct
28 Correct 430 ms 25076 KB Output is correct
29 Correct 425 ms 24628 KB Output is correct
30 Correct 463 ms 24812 KB Output is correct
31 Correct 455 ms 24920 KB Output is correct
32 Correct 430 ms 21156 KB Output is correct
33 Correct 0 ms 204 KB Output is correct