Submission #1023736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023736		manizare	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	510 ms	33056 KiB

worst_reporter3

#include <bits/stdc++.h>
 
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 10  , sq = 550,  inf = 1e8+10 , mod = 10007 , lg = 20  ;
int n , q , d[maxn] , s[maxn] , t[maxn] ; 

int que(int x , int f){
    int l = -1 , r = n+1 ;
    while(r-l>1){
        int m =(l+r)/2 ;
        int ted = f/t[m] ;
        int x2 = -m + ted * s[m] ; 
        if(x2 <= x){
            r = m ; 
        }else{
            l = m ;
        }  
    }
    return n+1-r ; 
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);    
    cin >> n >> q ; 
    s[0] = t[0] = 1;bool ok = 0;  
    rep(i ,1 , n){
        cin>> d[i] ; 
        if(ok == 1)continue ; 
        int ted = (d[i] + s[i-1]-1)/s[i-1] ; 
        s[i] = ted * s[i-1]; 
        t[i] = ted * t[i-1] ; 
        if(t[i] > 1e9){
            ok = 1 ;
            rep(j , i+1 , n)t[j] = t[j-1] ; 

        }
    }
    while(q--){
        int l , r , ti ;cin >> ti >> l >> r; 
        cout << que(r , ti) - que(l-1 ,ti) << "\n" ; 
    }   
}
/*
*/

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81