oj.uz

Submission #135148

# Submission time Handle Problem Language Result Execution time Memory
135148 2019-07-23T17:03:13 Z doowey Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 964 ms 8824 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
const int N = (int)5e5 + 9;
const ll MAX = (ll)2e18;
ll per[N];

ll compute(int id, ll tim){
    return (tim-(tim%per[id]))-id;
}

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    cin >> per[1];
    for(int i = 2; i <= n; i ++ ){
        cin >> per[i];
        per[i] = (per[i - 1] * (((per[i] - 1) / per[i-1]) + 1));
    }
    ll L, R, T;
    int lf, rf, md;
    int p1, p2;
    for(int i = 0 ; i < q; i ++ ){
        cin >> T >> L >> R;
        lf = 0;
        rf = n + 1;
        while(lf + 1 < rf){
            md=(lf+rf)/2;
            if(compute(md, T) < L)
                rf = md;
            else
                lf = md;
        }
        p1 = lf;
        lf = 0;
        rf = n + 1;
        while(lf + 1 < rf){
            md = (lf + rf) / 2;
            if(compute(md, T) > R){
                lf = md;
            }
            else{
                rf = md;
            }
        }
        p2 = lf;
        cout << max(0, p1 - p2) + (T >= L && T <= R) << "\n";
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 8436 KB Output is correct
2 Correct 891 ms 8360 KB Output is correct
3 Correct 870 ms 8232 KB Output is correct
4 Correct 874 ms 8524 KB Output is correct
5 Correct 903 ms 8728 KB Output is correct
6 Correct 871 ms 8756 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 8436 KB Output is correct
2 Correct 891 ms 8360 KB Output is correct
3 Correct 870 ms 8232 KB Output is correct
4 Correct 874 ms 8524 KB Output is correct
5 Correct 903 ms 8728 KB Output is correct
6 Correct 871 ms 8756 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 544 ms 6632 KB Output is correct
14 Correct 551 ms 5752 KB Output is correct
15 Correct 524 ms 6648 KB Output is correct
16 Correct 551 ms 6776 KB Output is correct
17 Correct 691 ms 7160 KB Output is correct
18 Correct 704 ms 7052 KB Output is correct
19 Correct 691 ms 7004 KB Output is correct
20 Correct 727 ms 7136 KB Output is correct
21 Correct 695 ms 7060 KB Output is correct
22 Correct 690 ms 7104 KB Output is correct
23 Correct 693 ms 7032 KB Output is correct
24 Correct 686 ms 7160 KB Output is correct
25 Correct 861 ms 8676 KB Output is correct
26 Correct 845 ms 8824 KB Output is correct
27 Correct 745 ms 7556 KB Output is correct
28 Correct 707 ms 7416 KB Output is correct
29 Correct 708 ms 7388 KB Output is correct
30 Correct 744 ms 7540 KB Output is correct
31 Correct 740 ms 7460 KB Output is correct
32 Correct 682 ms 7836 KB Output is correct
33 Correct 2 ms 376 KB Output is correct