oj.uz

Submission #67162

# Submission time Handle Problem Language Result Execution time Memory
67162 2018-08-13T12:42:15 Z imeimi2000 Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 1285 ms 263168 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
llong d[500001];

int getPos(int i, int t) {
    return i - t / d[i] * d[i];
}

int lowbound(int x, int t) {
    int s = 0, e = n + 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (getPos(m, t) < x) s = m + 1;
        else e = m;
    }
    return s;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int q;
	cin >> n >> q;
	d[0] = 1;
	for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        d[i] = ((d[i] - 1) / d[i - 1] + 1) * d[i - 1];
	}
	
	while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        printf("%d\n", lowbound(-l + 1, t) - lowbound(-r, t));
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 22908 KB Output is correct
2 Correct 1134 ms 38224 KB Output is correct
3 Correct 1253 ms 53920 KB Output is correct
4 Correct 1210 ms 69456 KB Output is correct
5 Correct 1278 ms 84920 KB Output is correct
6 Correct 1285 ms 100360 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 22908 KB Output is correct
2 Correct 1134 ms 38224 KB Output is correct
3 Correct 1253 ms 53920 KB Output is correct
4 Correct 1210 ms 69456 KB Output is correct
5 Correct 1278 ms 84920 KB Output is correct
6 Correct 1285 ms 100360 KB Output is correct
7 Correct 4 ms 100360 KB Output is correct
8 Correct 4 ms 100360 KB Output is correct
9 Correct 4 ms 100360 KB Output is correct
10 Correct 5 ms 100360 KB Output is correct
11 Correct 4 ms 100360 KB Output is correct
12 Correct 3 ms 100360 KB Output is correct
13 Correct 755 ms 114600 KB Output is correct
14 Correct 626 ms 131172 KB Output is correct
15 Correct 639 ms 146496 KB Output is correct
16 Correct 695 ms 162260 KB Output is correct
17 Correct 901 ms 182352 KB Output is correct
18 Correct 962 ms 200716 KB Output is correct
19 Correct 985 ms 219496 KB Output is correct
20 Correct 903 ms 238188 KB Output is correct
21 Correct 935 ms 256776 KB Output is correct
22 Runtime error 979 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
23 Halted 0 ms 0 KB -