Submission #797900

# Submission time Handle Problem Language Result Execution time Memory
797900 2023-07-30T05:48:09 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++17
0 / 100
206 ms 14228 KB
#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';
    }
}
# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 14228 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 14228 KB Output isn't correct
2 Halted 0 ms 0 KB -