Submission #1283997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283997		Icelast	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	207 ms	12112 KiB

worst_reporter3

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct item{
    ll l, r, d;
};
void solve(){
    int n, q;
    cin >> n >> q;
    vector<ll> a(n+1), b(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    b[0] = 1;
    for(int i = 1; i <= n; i++){
        ll t = a[i] / b[i-1];
        b[i] = t * b[i-1];
        if(a[i] % b[i-1] != 0) b[i] += b[i-1];
    }
    for(int i = 1; i <= n; i++){
        ll t = a[i] / b[i-1];
        b[i] = t * b[i-1];
        if(a[i] % b[i-1] != 0) b[i] += b[i-1];
    }
    b.push_back(INF);
    vector<item> c;
    int len = 0;
    for(int i = 0; i <= n; i++){
        len++;
        if(b[i] != b[i+1]){
            c.push_back({-i, -i+len-1, b[i]});
            len = 0;
        }
    }

    for(int i = 1; i <= q; i++){
        ll l, r, t;
        cin >> t >> l >> r;
        ll ans = 0;
        for(auto it : c){
            ll delta = t / it.d;
            delta *= it.d;
            it.l += delta;
            it.r += delta;
            ll U = min(it.r, r) - max(it.l, l) + 1;
            U = max(U, 0LL);
            ans += U;
        }
        cout << ans << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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