oj.uz

Submission #914926

# Submission time Handle Problem Language Result Execution time Memory
914926 2024-01-23T00:28:29 Z yhkhoo Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 470 ms 26708 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    int d[n];
    for(int i=0; i<n; i++){
        cin >> d[i];
    }
    int cyc[n+1];
    int running=1;
    for(int i=0; i<=n; i++){
        if(running <= 1000000000){
            cyc[i] = running;
            running *= d[i]/running + (d[i]%running != 0);
        }
        else{
            cyc[i] = 0;
        }
    }
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        int lo=0, hi=n, m1;
        while(lo<hi){
            m1 = (lo+hi)/2;
            if(hi-lo == 1) m1++;
            int ccyc = cyc[m1];
            int tra = (t/ccyc) * ccyc;
            tra -= m1;
            if(tra < l){
                hi = m1-1;
            }
            else if(tra > l){
                lo = m1;
            }
            else{
                lo = m1;
                hi = m1;
            }
        }
        m1 = lo;
        if(m1 == 0 && t<l){
            m1--;
        }
        lo = 0;
        hi = n;
        int m2 = lo;
        while(lo<hi){
            m2 = (lo+hi)/2;
            if(hi-lo == 1) m2++;
            int ccyc = cyc[m2];
            int tra = (t/ccyc) * ccyc;
            tra -= m2;
            if(tra <= r){
                hi = m2-1;
            }
            else{
                lo = m2;
            }
        }
        m2 = lo;
        if(m2 == 0 && t<=r){
            m2--;
        }
        cout << m1-m2 << '\n';
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 25636 KB Output is correct
2 Correct 437 ms 26708 KB Output is correct
3 Correct 435 ms 26704 KB Output is correct
4 Correct 439 ms 26708 KB Output is correct
5 Correct 443 ms 26708 KB Output is correct
6 Correct 446 ms 26672 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 25636 KB Output is correct
2 Correct 437 ms 26708 KB Output is correct
3 Correct 435 ms 26704 KB Output is correct
4 Correct 439 ms 26708 KB Output is correct
5 Correct 443 ms 26708 KB Output is correct
6 Correct 446 ms 26672 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 484 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Runtime error 58 ms 21224 KB Execution killed with signal 8
14 Halted 0 ms 0 KB -