oj.uz

Submission #624584

# Submission time Handle Problem Language Result Execution time Memory
624584 2022-08-08T13:53:44 Z radal Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 539 ms 25368 KB 
//why I missed it
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr ll N = 5e5+10,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}
int d[N];
int a[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    a[0] = 1;
    rep(i,1,n+1){
        cin >> d[i];
        int cnt = (d[i]+a[i-1]-1)/a[i-1];
        ll cal1 = 1ll*a[i-1]*cnt;
        if (cal1 < inf) a[i] = cal1;
        else a[i] = inf;
    }
    while(q--){
        int t,x,y;
        cin >> t >> x >> y;
        int l = -1,r = n+1,m;
        while(r-l > 1){
            m = (l+r) >> 1;
            int cnt = t/a[m];
            ll po = 1ll*cnt*a[m]-m;
            if (po > y) l = m;
            else r = m;
        }
        int ans = -r;
        x--;
        l = -1;
        r = n+1;
        while(r-l > 1){
            m = (l+r) >> 1;
            int cnt = t/a[m];
            ll po = 1ll*cnt*a[m]-m;
            if (po > x) l = m;
            else r = m;
        }
        ans += r;
        cout << ans << endl;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 22604 KB Output is correct
2 Correct 517 ms 22616 KB Output is correct
3 Correct 512 ms 22600 KB Output is correct
4 Correct 508 ms 22612 KB Output is correct
5 Correct 517 ms 22860 KB Output is correct
6 Correct 530 ms 22568 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 22604 KB Output is correct
2 Correct 517 ms 22616 KB Output is correct
3 Correct 512 ms 22600 KB Output is correct
4 Correct 508 ms 22612 KB Output is correct
5 Correct 517 ms 22860 KB Output is correct
6 Correct 530 ms 22568 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 377 ms 21152 KB Output is correct
14 Correct 375 ms 21708 KB Output is correct
15 Correct 367 ms 20468 KB Output is correct
16 Correct 369 ms 20940 KB Output is correct
17 Correct 422 ms 25152 KB Output is correct
18 Correct 444 ms 25164 KB Output is correct
19 Correct 440 ms 25300 KB Output is correct
20 Correct 438 ms 25156 KB Output is correct
21 Correct 456 ms 25300 KB Output is correct
22 Correct 431 ms 25240 KB Output is correct
23 Correct 421 ms 25264 KB Output is correct
24 Correct 414 ms 25368 KB Output is correct
25 Correct 539 ms 22716 KB Output is correct
26 Correct 531 ms 22732 KB Output is correct
27 Correct 457 ms 24820 KB Output is correct
28 Correct 438 ms 25104 KB Output is correct
29 Correct 435 ms 24764 KB Output is correct
30 Correct 451 ms 24848 KB Output is correct
31 Correct 442 ms 25076 KB Output is correct
32 Correct 438 ms 21332 KB Output is correct
33 Correct 0 ms 340 KB Output is correct