oj.uz

Submission #358764

# Submission time Handle Problem Language Result Execution time Memory
358764 2021-01-26T05:39:35 Z ijxjdjd Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 698 ms 27500 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(5e5) + 5;
int D[MAXN];
ll moving[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, Q;
	cin >> N >> Q;
    moving[0] = 1;
	for (int i = 1; i <= N; i++) {
        cin >> D[i];
        moving[i] = ((moving[i-1] + D[i]-1)/moving[i-1])*moving[i-1];
	}
	auto getAt = [&] (ll time, int i) {
            return (time/moving[i]) * moving[i] - i;
    };
	FR(i, Q) {
        int t, l, r;
        cin >> t >> l >> r;
        if (getAt(t, 0) < l || getAt(t, N) > r) {
            cout << 0 << '\n';
            continue;
        }
        int low = 0;
        int high = N;
        while (low < high) {
            int mid = (low + high+1)/2;
            if (getAt(t, mid) >= l) {
                low = mid;
            }
            else {
                high = mid-1;
            }
        }
        int slow = low;
        low = 0; high = N;
        while (low < high) {
            int mid = (low + high)/2;
            if (getAt(t, mid) <= r) {
                high = mid;
            }
            else {
                low = mid+1;
            }
        }
        cout << slow-high + 1 << '\n';
	}

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 24812 KB Output is correct
2 Correct 668 ms 24684 KB Output is correct
3 Correct 633 ms 24940 KB Output is correct
4 Correct 621 ms 24812 KB Output is correct
5 Correct 621 ms 24652 KB Output is correct
6 Correct 625 ms 24784 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 24812 KB Output is correct
2 Correct 668 ms 24684 KB Output is correct
3 Correct 633 ms 24940 KB Output is correct
4 Correct 621 ms 24812 KB Output is correct
5 Correct 621 ms 24652 KB Output is correct
6 Correct 625 ms 24784 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 378 ms 23148 KB Output is correct
14 Correct 377 ms 23788 KB Output is correct
15 Correct 377 ms 22636 KB Output is correct
16 Correct 391 ms 23020 KB Output is correct
17 Correct 479 ms 27372 KB Output is correct
18 Correct 482 ms 27244 KB Output is correct
19 Correct 476 ms 27372 KB Output is correct
20 Correct 488 ms 27244 KB Output is correct
21 Correct 514 ms 27244 KB Output is correct
22 Correct 485 ms 27372 KB Output is correct
23 Correct 474 ms 27500 KB Output is correct
24 Correct 478 ms 27432 KB Output is correct
25 Correct 675 ms 24736 KB Output is correct
26 Correct 698 ms 24812 KB Output is correct
27 Correct 526 ms 26860 KB Output is correct
28 Correct 529 ms 27116 KB Output is correct
29 Correct 542 ms 26724 KB Output is correct
30 Correct 557 ms 26860 KB Output is correct
31 Correct 556 ms 27116 KB Output is correct
32 Correct 493 ms 23276 KB Output is correct
33 Correct 1 ms 364 KB Output is correct