oj.uz

Submission #364756

# Submission time Handle Problem Language Result Execution time Memory
364756 2021-02-09T21:57:01 Z jainbot27 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 769 ms 33388 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int n, q;
vl a;
vl p;
vl t;

ll pos(int idx, ll time){
    ll num = time / t[idx];
    return num*p[idx]-idx;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    a=p=t=vl(n+1);
    FOR(i, 1, 1+n){
        cin >> a[i];
    }
    p[0] = 1;
    t[0] = 1;
    FOR(i, 1, 1+n){
        // so we need to know how many days it will take to go dist
        // clearly we just wait when the distance is a[i]+1 or more -> which means its just when they travel a[i]?
        // so we need the number of periods
        ll per = (p[i-1]+a[i]-1)/p[i-1];
        p[i] = per*p[i-1];
        t[i] = per*t[i-1];
    }
    while(q--){
        ll t, l, r;
        cin >> t >> l >> r;
        int L = 0, R = n;
        int mn=-MOD, mx=MOD;
        while(L<=R){
            int M = (L+R)/2;
            //cout << M << ' ' << t << ' ' << pos(M, t) << nl;
            if(pos(M, t) >= l){
                mn = M;
                L = M+1;
            }
            else{
                R = M-1;
            }
        }
        L = 0, R = n;
        while(L<=R){
            int M = (L+R)/2;
            if(pos(M, t) <= r){
                mx = M;
                R = M-1;
            }
            else{
                L = M+1;
            }
        }
        //cout << mn << ' ' << mx << nl;
        cout << max(0, mn-mx+1) << nl;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 30572 KB Output is correct
2 Correct 742 ms 30576 KB Output is correct
3 Correct 752 ms 30700 KB Output is correct
4 Correct 736 ms 30828 KB Output is correct
5 Correct 746 ms 30700 KB Output is correct
6 Correct 728 ms 30572 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 30572 KB Output is correct
2 Correct 742 ms 30576 KB Output is correct
3 Correct 752 ms 30700 KB Output is correct
4 Correct 736 ms 30828 KB Output is correct
5 Correct 746 ms 30700 KB Output is correct
6 Correct 728 ms 30572 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 378 ms 29024 KB Output is correct
14 Correct 393 ms 29932 KB Output is correct
15 Correct 367 ms 28424 KB Output is correct
16 Correct 378 ms 28928 KB Output is correct
17 Correct 487 ms 33388 KB Output is correct
18 Correct 497 ms 33132 KB Output is correct
19 Correct 507 ms 33280 KB Output is correct
20 Correct 486 ms 33144 KB Output is correct
21 Correct 498 ms 33388 KB Output is correct
22 Correct 525 ms 33388 KB Output is correct
23 Correct 493 ms 33176 KB Output is correct
24 Correct 490 ms 33260 KB Output is correct
25 Correct 748 ms 30700 KB Output is correct
26 Correct 714 ms 30700 KB Output is correct
27 Correct 554 ms 32780 KB Output is correct
28 Correct 512 ms 33132 KB Output is correct
29 Correct 551 ms 32904 KB Output is correct
30 Correct 544 ms 32876 KB Output is correct
31 Correct 539 ms 33032 KB Output is correct
32 Correct 526 ms 29292 KB Output is correct
33 Correct 1 ms 364 KB Output is correct