oj.uz

Submission #774927

# Submission time Handle Problem Language Result Execution time Memory
774927 2023-07-06T05:55:13 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1362 ms 11744 KB 
#include <bits/stdc++.h>
#define int long long
 
using namespace std;
const int maxn = 5e5 + 5;
 
int n, q;
int f[maxn];
int d[maxn];
 
void open(){
    if(fopen("input.inp", "r")){
        freopen("input.inp", "r", stdin);
		
    }
}
 
signed main(){
    open();
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> d[i];
    }
 
    f[0] = 1;
    for(int i = 1; i <= n; i++){
        f[i] = ceil((double)(d[i]) / (double)(f[i - 1])) * f[i - 1];
    }
 
    auto get = [&](int pos, int t){
        return t / f[pos] * f[pos] - pos;
    };
 
    auto bin_sex = [&](int limit, int t){
        int s = 0, e = n;
        int ans = -1;
        while(s <= e){
            int mid = (s + e) >> 1;
            int pos = get(mid, t);
            // cout << t << " " << mid << " " << pos << endl;
            if(pos >= limit){
                s = mid + 1;
                ans = mid;
            }else{
                e = mid - 1;
            }
        }
        return ans + 1;
    };
 
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        if(t <= l){
            cout << (t == l) << endl;
        }else{
            cout << bin_sex(l, t) - bin_sex(r + 1, t) << endl;
        }
    }
 
    return 0;
}

Compilation message

worst_reporter3.cpp: In function 'void open()':
worst_reporter3.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("input.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1239 ms 11236 KB Output is correct
2 Correct 1281 ms 11012 KB Output is correct
3 Correct 1269 ms 11108 KB Output is correct
4 Correct 1264 ms 11104 KB Output is correct
5 Correct 1273 ms 11232 KB Output is correct
6 Correct 1283 ms 11112 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1239 ms 11236 KB Output is correct
2 Correct 1281 ms 11012 KB Output is correct
3 Correct 1269 ms 11108 KB Output is correct
4 Correct 1264 ms 11104 KB Output is correct
5 Correct 1273 ms 11232 KB Output is correct
6 Correct 1283 ms 11112 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 1092 ms 9072 KB Output is correct
14 Correct 1087 ms 9088 KB Output is correct
15 Correct 1046 ms 9072 KB Output is correct
16 Correct 1100 ms 9068 KB Output is correct
17 Correct 1326 ms 10468 KB Output is correct
18 Correct 1202 ms 10536 KB Output is correct
19 Correct 1280 ms 10608 KB Output is correct
20 Correct 1324 ms 10444 KB Output is correct
21 Correct 1362 ms 10472 KB Output is correct
22 Correct 1290 ms 10420 KB Output is correct
23 Correct 1358 ms 10556 KB Output is correct
24 Correct 1224 ms 10552 KB Output is correct
25 Correct 1270 ms 11112 KB Output is correct
26 Correct 1275 ms 11060 KB Output is correct
27 Correct 1256 ms 10948 KB Output is correct
28 Correct 1200 ms 10836 KB Output is correct
29 Correct 1254 ms 10968 KB Output is correct
30 Correct 1291 ms 11308 KB Output is correct
31 Correct 1244 ms 11328 KB Output is correct
32 Correct 1185 ms 11744 KB Output is correct
33 Correct 1 ms 212 KB Output is correct