oj.uz

Submission #756883

# Submission time Handle Problem Language Result Execution time Memory
756883 2023-06-12T11:01:18 Z ParsaS Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 321 ms 25332 KB 
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 5e5 + 5;
int n, q, d[N];

void solve() {
    cin >> n >> q;
    vector<pair<int, pair<int, int> > > vec;
    vec.pb({1, {0, 0}});
    d[0] = 1;
    bool tmp = false;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        if (tmp)
            continue;
        if (d[i] <= vec.back().fi) {
            vec.back().se.fi--;
        }
        int c = (d[i] + vec.back().fi - 1) / vec.back().fi;
        if (d[i] > vec.back().fi && c <= 3e9 / vec.back().fi) {
            vec.pb({c * vec.back().fi, {-i, -i}});
        }
        else if (d[i] > vec.back().fi)
            tmp = true;
    }
    while (q--) {
        ll t, l, r; cin >> t >> l >> r;

        int ans = 0;
        for (auto [a, b] : vec) {
            t /= a;
            t *= a;
            ll lt = b.fi + t, rt = b.se + t;
            ans += max(0LL, min(rt, r) - max(lt, l) + 1);
        }
        cout << ans << '\n';
    }

}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 7276 KB Output is correct
2 Correct 207 ms 7272 KB Output is correct
3 Correct 195 ms 7404 KB Output is correct
4 Correct 195 ms 7356 KB Output is correct
5 Correct 195 ms 7284 KB Output is correct
6 Correct 195 ms 7288 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 7276 KB Output is correct
2 Correct 207 ms 7272 KB Output is correct
3 Correct 195 ms 7404 KB Output is correct
4 Correct 195 ms 7356 KB Output is correct
5 Correct 195 ms 7284 KB Output is correct
6 Correct 195 ms 7288 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 228 ms 21104 KB Output is correct
14 Correct 218 ms 21848 KB Output is correct
15 Correct 221 ms 20432 KB Output is correct
16 Correct 218 ms 20916 KB Output is correct
17 Correct 305 ms 25164 KB Output is correct
18 Correct 299 ms 25216 KB Output is correct
19 Correct 301 ms 25260 KB Output is correct
20 Correct 308 ms 25140 KB Output is correct
21 Correct 282 ms 25196 KB Output is correct
22 Correct 301 ms 25240 KB Output is correct
23 Correct 292 ms 25124 KB Output is correct
24 Correct 309 ms 25332 KB Output is correct
25 Correct 210 ms 22700 KB Output is correct
26 Correct 218 ms 22720 KB Output is correct
27 Correct 302 ms 25032 KB Output is correct
28 Correct 319 ms 25140 KB Output is correct
29 Correct 320 ms 24652 KB Output is correct
30 Correct 306 ms 24740 KB Output is correct
31 Correct 321 ms 24956 KB Output is correct
32 Correct 211 ms 21216 KB Output is correct
33 Correct 1 ms 212 KB Output is correct