oj.uz

Submission #994412

# Submission time Handle Problem Language Result Execution time Memory
994412 2024-06-07T14:56:28 Z onbert Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 173 ms 18860 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, INF = 1e9;
int n;
vector<pair<int,int>> a;
int cnt(int x, int t) {
    int l = 0, r = a.size()-2;
    while (l<r) {
        int mid = (l+r+1)/2;
        if (a[mid].second + (t - t%a[mid].first) >= x) l = mid;
        else r = mid-1;
    }
    // cout << "test " << x << " " << t << " " << l << endl;
    int pos = a[l].second + (t - t%a[l].first);
    if (pos < x) return 0;
    return min(pos - x, a[l].second - a[l+1].second-1) + (-a[l].second + 1);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n >> q;
    int cur = 0;
    a.push_back({1, 0});
    for (int i=1;i<=n;i++) {
        int x;
        cin >> x;
        if (x > cur && cur <= INF) {
            if (cur==0) cur = x;
            else cur = ((x+cur-1)/cur) * cur;
            if (cur <= INF) a.push_back({cur, -i});
        }
    }
    a.push_back({1e18, -n-1});
    // for (auto [x, y]:a) cout << x << " " << y << endl;
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << cnt(l, t) - cnt(r+1, t) << "\n";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 18772 KB Output is correct
2 Correct 173 ms 18772 KB Output is correct
3 Correct 149 ms 18684 KB Output is correct
4 Correct 155 ms 18860 KB Output is correct
5 Correct 143 ms 18772 KB Output is correct
6 Correct 148 ms 18772 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 18772 KB Output is correct
2 Correct 173 ms 18772 KB Output is correct
3 Correct 149 ms 18684 KB Output is correct
4 Correct 155 ms 18860 KB Output is correct
5 Correct 143 ms 18772 KB Output is correct
6 Correct 148 ms 18772 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 155 ms 17496 KB Output isn't correct
14 Halted 0 ms 0 KB -