Submission #242545

#	Time	Username	Problem	Language	Result	Execution time	Memory
242545		lyc	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	933 ms	29304 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 5e5+5;
const int mxQ = 5e5+5;
const int mxT = 2e9;

int N, Q, D[mxN];
int W[mxN], Len[mxN], pW[mxN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    FOR(i,1,N){
        cin >> D[i];
    }
    Len[0] = 1;
    W[0] = 1;
    pW[0] = 1;
    FOR(i,1,N){
        W[i] = (D[i]-1)/Len[i-1] + 1;
        { ll tmp = (ll) pW[i-1] * W[i];
        if (tmp > mxT) pW[i] = -1;
        else pW[i] = tmp; }
        { ll tmp = (ll) W[i] * Len[i-1];
        if (tmp > mxT) Len[i] = -1;
        else Len[i] = tmp; }
        //TRACE(W[i] _ Len[i] _ pW[i]);
    }

    FOR(i,1,Q){
        int T, L, R; cin >> T >> L >> R;

        int fst, lst;
        { int lo = -1, hi = N+1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            if (pW[mid] == -1 || (ll)T/pW[mid]*Len[mid] - mid <= R) hi = mid;
            else lo = mid;
        } 
        fst = hi; }
        { int lo = -1, hi = N+1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            if (pW[mid] == -1 || (ll)T/pW[mid]*Len[mid] - mid < L) hi = mid;
            else lo = mid;
        } 
        lst = hi; }
        cout << lst-fst << '\n';
    }
}

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