oj.uz

Submission #135147

# Submission time Handle Problem Language Result Execution time Memory
135147 2019-07-23T16:59:59 Z doowey Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 905 ms 25548 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;
    ll res;
    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){
                rf = md;
            }
            else{
                lf = md;
            }
        }
        p2 = lf;
        cout << max(0, p1 - p2) + (T >= L && T <= R) << "\n";
    }
    return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:32:8: warning: unused variable 'res' [-Wunused-variable]
     ll res;
        ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 7544 KB Output is correct
2 Correct 904 ms 22752 KB Output is correct
3 Correct 889 ms 22820 KB Output is correct
4 Correct 905 ms 22732 KB Output is correct
5 Correct 870 ms 22880 KB Output is correct
6 Correct 879 ms 22636 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 879 ms 7544 KB Output is correct
2 Correct 904 ms 22752 KB Output is correct
3 Correct 889 ms 22820 KB Output is correct
4 Correct 905 ms 22732 KB Output is correct
5 Correct 870 ms 22880 KB Output is correct
6 Correct 879 ms 22636 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 543 ms 21192 KB Output is correct
14 Correct 551 ms 21900 KB Output is correct
15 Correct 523 ms 20472 KB Output is correct
16 Correct 544 ms 21116 KB Output is correct
17 Correct 702 ms 25196 KB Output is correct
18 Correct 698 ms 25208 KB Output is correct
19 Correct 711 ms 25548 KB Output is correct
20 Correct 698 ms 25316 KB Output is correct
21 Correct 699 ms 25272 KB Output is correct
22 Correct 724 ms 25464 KB Output is correct
23 Correct 710 ms 25400 KB Output is correct
24 Correct 695 ms 25436 KB Output is correct
25 Correct 875 ms 22868 KB Output is correct
26 Correct 882 ms 22776 KB Output is correct
27 Correct 743 ms 24896 KB Output is correct
28 Correct 723 ms 25316 KB Output is correct
29 Correct 740 ms 24708 KB Output is correct
30 Correct 766 ms 24952 KB Output is correct
31 Correct 747 ms 25232 KB Output is correct
32 Correct 681 ms 21316 KB Output is correct
33 Correct 2 ms 376 KB Output is correct