답안 #644028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
644028	2022-09-23T13:51:24 Z	someone	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	542 ms	22972 KB

worst_reporter3

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1 << 19, INF = 1e18 + 42;

int n, q, period[N];

int dicho(int t, int obj) {
    int ans = -1;
    for(int i = 18; i >= 0; i--)
        if(period[ans + (1 << i)] * (t / period[ans + (1 << i)]) - ans - (1 << i) >= obj)
            ans += (1 << i);
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> q;
    
    n++;
    period[0] = 1;
    for(int i = 1; i < n; i++) {
        cin >> period[i];
        period[i] = ((period[i] + period[i-1] - 1) / period[i-1]) * period[i-1];
    }
    for(int i = n; i < N; i++)
        period[i] = INF;
    for(int i = 0; i < q; i++) {
        int t, l, r; cin >> t >> l >> r;
        cout << dicho(t, l) - dicho(t, r+1) << '\n';
    }
}

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	517 ms	22812 KB	Output is correct
2	Correct	525 ms	22860 KB	Output is correct
3	Correct	516 ms	22972 KB	Output is correct
4	Correct	542 ms	22832 KB	Output is correct
5	Correct	527 ms	22880 KB	Output is correct
6	Correct	532 ms	22860 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4436 KB	Output is correct
2	Correct	2 ms	4428 KB	Output is correct
3	Correct	2 ms	4436 KB	Output is correct
4	Correct	2 ms	4308 KB	Output is correct
5	Correct	3 ms	4436 KB	Output is correct
6	Correct	3 ms	4440 KB	Output is correct

Subtask #3

81.0 / 81.0

#	결과	실행 시간	메모리	Grader output
1	Correct	517 ms	22812 KB	Output is correct
2	Correct	525 ms	22860 KB	Output is correct
3	Correct	516 ms	22972 KB	Output is correct
4	Correct	542 ms	22832 KB	Output is correct
5	Correct	527 ms	22880 KB	Output is correct
6	Correct	532 ms	22860 KB	Output is correct
7	Correct	2 ms	4436 KB	Output is correct
8	Correct	2 ms	4428 KB	Output is correct
9	Correct	2 ms	4436 KB	Output is correct
10	Correct	2 ms	4308 KB	Output is correct
11	Correct	3 ms	4436 KB	Output is correct
12	Correct	3 ms	4440 KB	Output is correct
13	Correct	347 ms	21456 KB	Output is correct
14	Correct	341 ms	21836 KB	Output is correct
15	Correct	345 ms	20624 KB	Output is correct
16	Correct	345 ms	21068 KB	Output is correct
17	Correct	404 ms	8268 KB	Output is correct
18	Correct	393 ms	8256 KB	Output is correct
19	Correct	391 ms	8248 KB	Output is correct
20	Correct	400 ms	8404 KB	Output is correct
21	Correct	400 ms	8288 KB	Output is correct
22	Correct	388 ms	8464 KB	Output is correct
23	Correct	389 ms	8280 KB	Output is correct
24	Correct	392 ms	8376 KB	Output is correct
25	Correct	528 ms	22896 KB	Output is correct
26	Correct	524 ms	22852 KB	Output is correct
27	Correct	439 ms	11712 KB	Output is correct
28	Correct	418 ms	8648 KB	Output is correct
29	Correct	436 ms	12564 KB	Output is correct
30	Correct	443 ms	11296 KB	Output is correct
31	Correct	419 ms	8652 KB	Output is correct
32	Correct	432 ms	21428 KB	Output is correct
33	Correct	2 ms	4308 KB	Output is correct