oj.uz

Submission #205660

# Submission time Handle Problem Language Result Execution time Memory
205660 2020-02-29T11:43:38 Z Atill83 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 828 ms 30820 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 5e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, q;
ll D[MAXN];
ll per[MAXN];
ll del[MAXN];

ll gt(ll mes, ll time){
    ll l = 0, r = n + 1;
    while(l < r){
        ll m = (l + r)/2;
        if(-n + m + time/per[m]*del[m] <= mes){
            l = m + 1;
        }else{
            r = m;
        }
    }
    return l;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>q;

    for(int i = n - 1; i >= 0; i--){
        cin>>D[i];
    }
    D[n] = 1;
    del[n] = 1;
    per[n] = 1;
    del[n + 1] = mod;
    per[n + 1] = 1;
    D[n + 1] = 1;
    for(int i = n - 1; i >= 0; i--){
        per[i] = ((D[i] + del[i + 1] - 1)/del[i + 1])*per[i + 1];
        del[i] = per[i]/per[i + 1]*del[i + 1];
    }
    /*for(int i = 0; i <= n; i++){
        cout<<per[i]<<" "<<del[i]<<" "<<D[i]<<endl;
    }*/

    for(int i = 0; i < q; i++){
        ll l, r, T;
        cin>>T>>l>>r;
        cout<<gt(r, T) - gt(l - 1, T)<<endl;

    }



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 30584 KB Output is correct
2 Correct 828 ms 30712 KB Output is correct
3 Correct 813 ms 30712 KB Output is correct
4 Correct 805 ms 30820 KB Output is correct
5 Correct 808 ms 30732 KB Output is correct
6 Correct 821 ms 30584 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 5 ms 376 KB Output is correct
3 Correct 6 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 821 ms 30584 KB Output is correct
2 Correct 828 ms 30712 KB Output is correct
3 Correct 813 ms 30712 KB Output is correct
4 Correct 805 ms 30820 KB Output is correct
5 Correct 808 ms 30732 KB Output is correct
6 Correct 821 ms 30584 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 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 423 ms 29176 KB Output is correct
14 Correct 414 ms 22776 KB Output is correct
15 Correct 405 ms 28536 KB Output is correct
16 Correct 415 ms 29048 KB Output is correct
17 Correct 516 ms 15352 KB Output is correct
18 Correct 520 ms 15352 KB Output is correct
19 Correct 520 ms 15352 KB Output is correct
20 Correct 538 ms 15224 KB Output is correct
21 Correct 532 ms 15224 KB Output is correct
22 Correct 523 ms 15352 KB Output is correct
23 Correct 515 ms 15300 KB Output is correct
24 Correct 523 ms 15352 KB Output is correct
25 Correct 796 ms 30596 KB Output is correct
26 Correct 790 ms 30584 KB Output is correct
27 Correct 570 ms 15736 KB Output is correct
28 Correct 552 ms 16036 KB Output is correct
29 Correct 552 ms 15736 KB Output is correct
30 Correct 575 ms 15864 KB Output is correct
31 Correct 554 ms 15608 KB Output is correct
32 Correct 548 ms 29176 KB Output is correct
33 Correct 5 ms 376 KB Output is correct