Submission #1219964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219964		AlgorithmWarrior	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	169 ms	7360 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

int const TMAX=1e9;
int const NMAX=500005;
int n,q;
int dist[NMAX];
int speed[NMAX];

void read(){
    cin>>n>>q;
    int i;
    for(i=1;i<=n;++i)
        cin>>dist[i];
}

struct balls_interval{
    int spd,l,r;
};
vector<balls_interval>b_intv;

void precalc_speed(){
    speed[0]=1;
    int i;
    for(i=1;i<=n;++i){
        speed[i]=(dist[i]+speed[i-1]-1)/speed[i-1]*speed[i-1];
        if(speed[i]>TMAX)
            break;
    }
    speed[i]=TMAX+1;
    for(i=0;speed[i]<=TMAX;++i){
        int spd=speed[i],l=-i,r=-i;
        while(speed[i]==speed[i+1]){
            ++i;
            l=-i;
        }
        b_intv.push_back({spd,l,r});
    }
}

int inters(int l1,int r1,int l2,int r2){
    return max(0,min(r1,r2)-max(l1,l2)+1);
}

void process_queries(){
    while(q--){
        int timp,l,r;
        cin>>timp>>l>>r;
        int ans=0;
        for(auto [spd,lb,rb] : b_intv){
            int depl=timp/spd*spd;
            ans+=inters(lb+depl,rb+depl,l,r);
        }
        cout<<ans<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    precalc_speed();
    process_queries();
    return 0;
}

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