oj.uz

Submission #774735

# Submission time Handle Problem Language Result Execution time Memory
774735 2023-07-06T02:24:03 Z CDuong Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 452 ms 25252 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 5e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

int n, q, speed[mxN];

void solve() {
    cin >> n >> q; speed[0] = 1;
    for(int i = 1; i <= n; ++i) {
        int val; cin >> val;
        if(speed[i - 1] == mod) {
            speed[i] = mod;
            continue;
        }
        int needed = val / speed[i - 1];
        if(needed * speed[i - 1] < val) ++needed;
        if(mod / needed < speed[i - 1]) speed[i] = mod;
        else speed[i] = speed[i - 1] * needed;
    }
    for(int i = 1; i <= q; ++i) {
        int t, l, r; cin >> t >> l >> r;
        int tl = 0, tr = n, ansl = -1, ansr = -1;
        while(tl <= tr) {
            int mid = (tl + tr) >> 1;
            if(speed[mid] == -1) tr = mid - 1;
            else {
                int len = (t / speed[mid]) * speed[mid] - mid;
                if(len >= l) tl = mid + 1;
                else tr = mid - 1;
            }
        }
        if(tr < 0) {
            cout << 0 << "\n";
            continue;
        }
        else ansl = tr;

        tl = 0, tr = n;
        while(tl <= tr) {
            int mid = (tl + tr) >> 1;
            if(speed[mid] == -1) tr = mid - 1;
            else {
                int len = (t / speed[mid]) * speed[mid] - mid;
                // cout << len << " " << t << " " << speed[mid] << endl;
                if(len <= r) tr = mid - 1;
                else tl = mid + 1;
            }
        }
        // cout << ansl << " " << tl << endl;
        if(tl > ansl) cout << 0 << "\n";
        else cout << ansl - tl + 1 << "\n";
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Compilation message

worst_reporter3.cpp: In function 'void solve()':
worst_reporter3.cpp:43:40: warning: unused variable 'ansr' [-Wunused-variable]
   43 |         int tl = 0, tr = n, ansl = -1, ansr = -1;
      |                                        ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 22656 KB Output is correct
2 Correct 433 ms 22604 KB Output is correct
3 Correct 437 ms 22708 KB Output is correct
4 Correct 430 ms 22604 KB Output is correct
5 Correct 430 ms 22628 KB Output is correct
6 Correct 452 ms 22592 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 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 22656 KB Output is correct
2 Correct 433 ms 22604 KB Output is correct
3 Correct 437 ms 22708 KB Output is correct
4 Correct 430 ms 22604 KB Output is correct
5 Correct 430 ms 22628 KB Output is correct
6 Correct 452 ms 22592 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 258 ms 21144 KB Output is correct
14 Correct 262 ms 21676 KB Output is correct
15 Correct 248 ms 20356 KB Output is correct
16 Correct 258 ms 21036 KB Output is correct
17 Correct 322 ms 25120 KB Output is correct
18 Correct 321 ms 25200 KB Output is correct
19 Correct 349 ms 25244 KB Output is correct
20 Correct 320 ms 25160 KB Output is correct
21 Correct 329 ms 25200 KB Output is correct
22 Correct 324 ms 25232 KB Output is correct
23 Correct 334 ms 25252 KB Output is correct
24 Correct 331 ms 25172 KB Output is correct
25 Correct 425 ms 22604 KB Output is correct
26 Correct 431 ms 22656 KB Output is correct
27 Correct 373 ms 24780 KB Output is correct
28 Correct 350 ms 25024 KB Output is correct
29 Correct 354 ms 24564 KB Output is correct
30 Correct 353 ms 24720 KB Output is correct
31 Correct 366 ms 25072 KB Output is correct
32 Correct 339 ms 21164 KB Output is correct
33 Correct 1 ms 212 KB Output is correct