oj.uz

Submission #433213

# Submission time Handle Problem Language Result Execution time Memory
433213 2021-06-19T08:41:36 Z cpp219 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 677 ms 33236 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;
typedef pair<ll,ll> LL;

ll n,Q,x,pre[N],T,L,R,a[N],val[N];
ll Getpos(ll nTime,ll id){
    if (!id) return nTime;
    //cout<<nTime<<" "<<id <<" "<< val[id]<<"x\n";
    ll jump = nTime/(val[id]); //cout<<jump; exit(0);
    return jump * val[id] - id;
}

ll GetLast(){
    ll l,m,h; l = 0; h = n;
    while(l <= h){
        m = (l + h)/2; //cout<<Getpos(T,m)<<"x\n";
        if (Getpos(T,m) >= L) l = m + 1;
        else h = m - 1;
    }
    //exit(0);
    return h;
}

ll GetFirst(){
    ll l,m,h; l = 0; h = n;
    while(l <= h){
        m = (l + h)/2;
        if (Getpos(T,m) > R) l = m + 1;
        else h = m - 1;
    }
    return l;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++) cin>>x,pre[i] = (pre[i - 1] + x),a[i] = x;
    val[1] = a[1];
    for (ll i = 2;i <= n;i++){
        ll up = ceil((ld)a[i]/val[i - 1]);
        val[i] = val[i - 1]*up;
    }
    //cout<<Getpos(190,5); return 0;
    while(Q--){
        cin>>T>>L>>R;
        //for (ll i = 0;i <= n;i++) cout<<Getpos(T,i)<<" "; return 0;
        if (T < L) cout<<"0\n";
        else cout<<GetLast() - GetFirst() + 1<<"\n";
        //cout<<GetLast()<<" "<<GetFirst(); return 0;
    }
}

Compilation message

worst_reporter3.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
worst_reporter3.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 30532 KB Output is correct
2 Correct 641 ms 30456 KB Output is correct
3 Correct 658 ms 30428 KB Output is correct
4 Correct 649 ms 30528 KB Output is correct
5 Correct 648 ms 30552 KB Output is correct
6 Correct 653 ms 30500 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 30532 KB Output is correct
2 Correct 641 ms 30456 KB Output is correct
3 Correct 658 ms 30428 KB Output is correct
4 Correct 649 ms 30528 KB Output is correct
5 Correct 648 ms 30552 KB Output is correct
6 Correct 653 ms 30500 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 375 ms 28920 KB Output is correct
14 Correct 404 ms 29600 KB Output is correct
15 Correct 370 ms 28256 KB Output is correct
16 Correct 380 ms 28952 KB Output is correct
17 Correct 492 ms 33080 KB Output is correct
18 Correct 477 ms 33080 KB Output is correct
19 Correct 524 ms 33236 KB Output is correct
20 Correct 486 ms 32956 KB Output is correct
21 Correct 483 ms 33004 KB Output is correct
22 Correct 509 ms 33092 KB Output is correct
23 Correct 484 ms 32984 KB Output is correct
24 Correct 493 ms 33060 KB Output is correct
25 Correct 631 ms 30464 KB Output is correct
26 Correct 677 ms 30528 KB Output is correct
27 Correct 531 ms 32580 KB Output is correct
28 Correct 511 ms 32928 KB Output is correct
29 Correct 536 ms 32536 KB Output is correct
30 Correct 565 ms 32656 KB Output is correct
31 Correct 572 ms 32792 KB Output is correct
32 Correct 521 ms 29124 KB Output is correct
33 Correct 1 ms 332 KB Output is correct