Submission #799875

#	Time	Username	Problem	Language	Result	Execution time	Memory
799875		phoenix	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	320 ms	31148 KiB

worst_reporter3

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int M = 1e3 + 10;
const int N = 5e5 + 10;

int n, q;
ll d[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) 
        cin >> d[i];
    ll D[n + 1] = {};
    D[0] = 1;
    for(int i = 1; i <= n; i++) 
        D[i] = D[i - 1] * ((d[i] + D[i - 1] - 1)/ D[i - 1]);
    int nxt[n + 1] = {};
    nxt[n] = n + 1;
    for(int i = n - 1; i >= 0; i--) {
        nxt[i] = (D[i] == D[i + 1] ? nxt[i + 1] : i + 1);
    }
    // for(int i = 0; i <= n; i++) 
    //     cout << D[i] << ' ';
    // cout << '\n';
    for(int i = 1; i <= q; i++) {
        ll t, l, r;
        cin >> t >> l >> r;
        int x = 1, pos = t;
        ll ans = (l <= t && t <= r);
        while(x <= n) {
            ll pos_r = -x + (pos + x - 1) / D[x] * D[x];
            ll pos_l = pos_r - (nxt[x] - 1 - x);
            
            // cout << x << ' ' << nxt[x] << '\n';
            // cout << pos_l << ' ' << pos_r << '\n';

            ll lb = max(pos_l, l), rb = min(pos_r, r);
            ans += max(rb - lb + 1, 0ll);
            pos = pos_l;
            x = nxt[x];
        }
        cout << ans << '\n';
    }
}

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