oj.uz

Submission #44416

# Submission time Handle Problem Language Result Execution time Memory
44416 2018-04-02T04:54:40 Z aome Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 1190 ms 11712 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

int n, m;
int d[N];
int a[N];
vector< vector<int> > vec;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	a[0] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i];
		int tmp = (d[i] + (a[i - 1] - 1)) / a[i - 1];
		a[i] = tmp * a[i - 1];
	}
	vector<int> cur;
	cur.push_back(0);
	for (int i = 1; i <= n; ++i) {
		if (a[i] != a[cur.back()]) {
			vec.push_back(cur), cur.clear();
		}
		cur.push_back(i);
	}
	vec.push_back(cur);
	for (int i = 1; i <= m; ++i) {
		int t, l, r; cin >> t >> l >> r;
		int res = 0;
		for (int j = 0; j < vec.size(); ++j) {
			int tmp = t / a[vec[j][0]] * a[vec[j][0]];
			int l0 = -vec[j].back(), r0 = -vec[j][0];
			int l1 = l - tmp, r1 = r - tmp;
			l0 = max(l0, l1), r0 = min(r0, r1);
			res += max(0, r0 - l0 + 1);
		}
		cout << res << '\n';
	}
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); ++j) {
                   ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 11368 KB Output is correct
2 Correct 1190 ms 11536 KB Output is correct
3 Correct 1063 ms 11536 KB Output is correct
4 Correct 1029 ms 11540 KB Output is correct
5 Correct 1082 ms 11584 KB Output is correct
6 Correct 1081 ms 11712 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 11368 KB Output is correct
2 Correct 1190 ms 11536 KB Output is correct
3 Correct 1063 ms 11536 KB Output is correct
4 Correct 1029 ms 11540 KB Output is correct
5 Correct 1082 ms 11584 KB Output is correct
6 Correct 1081 ms 11712 KB Output is correct
7 Correct 6 ms 11712 KB Output is correct
8 Correct 4 ms 11712 KB Output is correct
9 Correct 5 ms 11712 KB Output is correct
10 Correct 4 ms 11712 KB Output is correct
11 Correct 4 ms 11712 KB Output is correct
12 Correct 4 ms 11712 KB Output is correct
13 Runtime error 2 ms 11712 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -