제출 #205660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205660		Atill83	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	828 ms	30820 KiB

worst_reporter3

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 5e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, q;
ll D[MAXN];
ll per[MAXN];
ll del[MAXN];

ll gt(ll mes, ll time){
    ll l = 0, r = n + 1;
    while(l < r){
        ll m = (l + r)/2;
        if(-n + m + time/per[m]*del[m] <= mes){
            l = m + 1;
        }else{
            r = m;
        }
    }
    return l;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>q;

    for(int i = n - 1; i >= 0; i--){
        cin>>D[i];
    }
    D[n] = 1;
    del[n] = 1;
    per[n] = 1;
    del[n + 1] = mod;
    per[n + 1] = 1;
    D[n + 1] = 1;
    for(int i = n - 1; i >= 0; i--){
        per[i] = ((D[i] + del[i + 1] - 1)/del[i + 1])*per[i + 1];
        del[i] = per[i]/per[i + 1]*del[i + 1];
    }
    /*for(int i = 0; i <= n; i++){
        cout<<per[i]<<" "<<del[i]<<" "<<D[i]<<endl;
    }*/

    for(int i = 0; i < q; i++){
        ll l, r, T;
        cin>>T>>l>>r;
        cout<<gt(r, T) - gt(l - 1, T)<<endl;

    }



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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