제출 #1228440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228440		a4n_	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	499 ms	34632 KiB

worst_reporter3

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 5e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
ll n, q, d[N], t[N], L[N], R[N];
pll dp[2][N];

void work() {
    cin>>n>>q;
    for(int i=1; i<=n; i++) cin>>d[i];

    for(int i=1; i<=q; i++) cin>>t[i]>>L[i]>>R[i];
    
    dp[0][0] = dp[1][0] = {1, 1};
    for(int i=1; i<=n; i++) {
        dp[0][i].F = dp[0][i-1].F + (dp[0][i-1].S > d[i] ? 0 : 
            ((d[i] - dp[0][i-1].S + dp[1][i-1].S - 1) / dp[1][i-1].S)*dp[1][i-1].F);
        
        dp[0][i].S = dp[0][i-1].S + 
            ((d[i] - dp[0][i-1].S + dp[1][i-1].S - 1) / dp[1][i-1].S) * dp[1][i-1].S;

        dp[1][i].F = (dp[1][i-1].F) + (dp[1][i-1].S > d[i] ? 0 : 
            ((d[i] - dp[1][i-1].S + dp[1][i-1].S - 1) / dp[1][i-1].S)*dp[1][i-1].F);
        
        dp[1][i].S = dp[1][i-1].S + 
            (((d[i] - dp[1][i-1].S + dp[1][i-1].S - 1) / dp[1][i-1].S)*dp[1][i-1].S);

        if(max({dp[1][i].F, dp[1][i].S, dp[0][i].F, dp[0][i].S}) > 1e9) {
            n = i-1;
            break;
        }
    }

    for(int i=1; i<=q; i++) {
        int l = -1, r = n + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if((t[i] >= dp[0][mid].F ? dp[0][mid].S : 0ll) + 
            max(0ll, (t[i] - dp[0][mid].F) / dp[1][mid].F) * dp[1][mid].S - (ll)mid <= R[i]) {
                r = mid;
            } else {
                l = mid;
            }
        }
        int res1 = r;
        l = -1, r = n + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if((t[i] >= dp[0][mid].F ? dp[0][mid].S : 0ll) + 
            max(0ll, (t[i] - dp[0][mid].F) / dp[1][mid].F) * dp[1][mid].S - (ll)mid >= L[i]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        r = res1;

        cout<<max(0ll, (ll)l - r + 1)<<endl;
    }
}

void reset_work() {
    return;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
 
    // cin>>t;
    int tc = 1;
    while(tc --) {
        work();
        reset_work();
    }
 
    return 0;
}

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