oj.uz

Submission #246865

# Submission time Handle Problem Language Result Execution time Memory
246865 2020-07-10T12:41:22 Z Osama_Alkhodairy Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 493 ms 23632 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 20944 KB Output is correct
2 Correct 319 ms 20948 KB Output is correct
3 Correct 334 ms 20816 KB Output is correct
4 Correct 304 ms 20752 KB Output is correct
5 Correct 293 ms 20816 KB Output is correct
6 Correct 307 ms 20836 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 20944 KB Output is correct
2 Correct 319 ms 20948 KB Output is correct
3 Correct 334 ms 20816 KB Output is correct
4 Correct 304 ms 20752 KB Output is correct
5 Correct 293 ms 20816 KB Output is correct
6 Correct 307 ms 20836 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 309 ms 19372 KB Output is correct
14 Correct 313 ms 19920 KB Output is correct
15 Correct 304 ms 18512 KB Output is correct
16 Correct 311 ms 19152 KB Output is correct
17 Correct 441 ms 23380 KB Output is correct
18 Correct 428 ms 23376 KB Output is correct
19 Correct 436 ms 23420 KB Output is correct
20 Correct 437 ms 23632 KB Output is correct
21 Correct 432 ms 23376 KB Output is correct
22 Correct 429 ms 23420 KB Output is correct
23 Correct 436 ms 23388 KB Output is correct
24 Correct 470 ms 23448 KB Output is correct
25 Correct 325 ms 20816 KB Output is correct
26 Correct 320 ms 20816 KB Output is correct
27 Correct 493 ms 22864 KB Output is correct
28 Correct 470 ms 23244 KB Output is correct
29 Correct 454 ms 22972 KB Output is correct
30 Correct 447 ms 22964 KB Output is correct
31 Correct 474 ms 23120 KB Output is correct
32 Correct 315 ms 19432 KB Output is correct
33 Correct 5 ms 384 KB Output is correct