Submission #246865

#	Time	Username	Problem	Language	Result	Execution time	Memory
246865		Osama_Alkhodairy	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	493 ms	23632 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, q;
vector <int> d;
vector <pair <int, int> > a;

int query(int t, int x){
    int ret = 0;
    int pos = 0;
    for(auto &i : a){
        int head = pos + t / i.first * i.first;
        if(head < x) break;
        ret += min(i.second, head - x + 1);
        pos -= i.second;
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    d.resize(n);
    for(auto &i : d) cin >> i;
    d.insert(d.begin(), 1);
    int prev = 1;
    for(auto &i : d){
        int t = (i + prev - 1) / prev;
        if(prev > (int)1e9 / t) break;
        prev *= t;
        if(a.size() && prev == a.back().first) a.back().second++;
        else a.push_back(make_pair(prev, 1));
    }
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        cout << query(t, l) - query(t, r + 1) << "\n";
    }
}

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