oj.uz

Submission #258295

# Submission time Handle Problem Language Result Execution time Memory
258295 2020-08-05T16:34:22 Z Fidisk Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 632 ms 29536 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e18
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define _cos(xxxx) cos(xxxx*acos(-1)/180)
#define _sin(xxxx) sin(xxxx*acos(-1)/180)
#define _tan(xxxx) tan(xxxx*acos(-1)/180)
#define PE cout<<fixed
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
 
const ld pi=acos(-1);

ll n,q,i,a[500009],b[500009],pos,t,lt,rt,l,r,mid,rres,lres;

int main(){
    IO;
    cin>>n>>q;
    for (i=1;i<=n;i++) {
        cin>>a[i];
    }
    b[0]=1;
    for (i=1;i<=n;i++) {
        b[i]=((a[i]+b[i-1]-1)/b[i-1])*b[i-1];
    }
    for (i=1;i<=q;i++) {
        cin>>t>>lt>>rt;
        l=-1;
        r=n+1;
        while ((l+1)!=r) {
            mid=(r+l)/2;
            pos=(t/b[mid])*b[mid]-mid;
            //cout<<l<<' '<<r<<' '<<mid<<' '<<pos<<'\n';
            if (pos>=lt) {
                l=mid;
            }
            else {
                r=mid;
            }
        }
        //cout<<l<<' '<<r<<'\n';
        rres=r;
        l=-1;
        r=n+1;
        while ((l+1)!=r) {
            mid=(r+l)/2;
            pos=(t/b[mid])*b[mid]-mid;
            //cout<<l<<' '<<r<<' '<<mid<<' '<<pos<<'\n';
            if (pos<=rt) {
                r=mid;
            }
            else {
                l=mid;
            }
        }
        //cout<<l<<' '<<r<<'\n';
        lres=r;
        cout<<rres-lres<<'\n';
        //cout<<"------------\n";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 26680 KB Output is correct
2 Correct 604 ms 26720 KB Output is correct
3 Correct 616 ms 26824 KB Output is correct
4 Correct 632 ms 26684 KB Output is correct
5 Correct 615 ms 26816 KB Output is correct
6 Correct 626 ms 26744 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 26680 KB Output is correct
2 Correct 604 ms 26720 KB Output is correct
3 Correct 616 ms 26824 KB Output is correct
4 Correct 632 ms 26684 KB Output is correct
5 Correct 615 ms 26816 KB Output is correct
6 Correct 626 ms 26744 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 403 ms 25464 KB Output is correct
14 Correct 398 ms 25976 KB Output is correct
15 Correct 373 ms 24440 KB Output is correct
16 Correct 397 ms 24952 KB Output is correct
17 Correct 511 ms 29176 KB Output is correct
18 Correct 470 ms 29176 KB Output is correct
19 Correct 493 ms 29432 KB Output is correct
20 Correct 491 ms 29176 KB Output is correct
21 Correct 498 ms 29176 KB Output is correct
22 Correct 480 ms 29304 KB Output is correct
23 Correct 486 ms 29320 KB Output is correct
24 Correct 486 ms 29536 KB Output is correct
25 Correct 605 ms 26744 KB Output is correct
26 Correct 606 ms 26744 KB Output is correct
27 Correct 520 ms 28792 KB Output is correct
28 Correct 520 ms 29176 KB Output is correct
29 Correct 516 ms 28820 KB Output is correct
30 Correct 583 ms 28920 KB Output is correct
31 Correct 524 ms 29048 KB Output is correct
32 Correct 487 ms 25464 KB Output is correct
33 Correct 0 ms 384 KB Output is correct