oj.uz

Submission #399934

# Submission time Handle Problem Language Result Execution time Memory
399934 2021-05-06T23:22:37 Z GioChkhaidze Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 357 ms 23500 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define pb push_back
#define f first
#define s second
 
using namespace std;
 
const int N = 5e5 + 5;
 
int n, q, d[N];
vector < pair < int , int > > v;
 
main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i];
	}
	
	int x = 1;
	for (int i = 1; i <= n; ++i) {
		if (!v.size() || x < d[i]) {
			v.pb({x * ((d[i] - 1) / x + 1), 1});
			x = v.back().f;
		}
			else
		if (d[i] <= x) {
			++v.back().s;		
		}
	}
	
	int t, l, r, sum, ans, L, R;
	for (int i = 1; i <= q; ++i) {
		cin >> t >> l >> r;
		if (t < l) {
			cout << 0 << "\n";
			continue;
		}
		
		sum = -1, ans = (l <= t && t <= r);
		for (int j = 0; j < v.size(); ++j) {
			R = t + (sum - t % v[j].f);
			L = R - v[j].s + 1;	
			if (R < l) break;
			if (R > r) R = r;
			if (L < l) L = l;
			if (L <= R) ans += R - L + 1;
			sum -= v[j].s;
		}
		
		cout << ans << "\n";
	}
}

Compilation message

worst_reporter3.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main () {
      |       ^
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j = 0; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 6340 KB Output is correct
2 Correct 274 ms 6288 KB Output is correct
3 Correct 258 ms 6372 KB Output is correct
4 Correct 254 ms 6288 KB Output is correct
5 Correct 254 ms 6364 KB Output is correct
6 Correct 254 ms 6336 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 6340 KB Output is correct
2 Correct 274 ms 6288 KB Output is correct
3 Correct 258 ms 6372 KB Output is correct
4 Correct 254 ms 6288 KB Output is correct
5 Correct 254 ms 6364 KB Output is correct
6 Correct 254 ms 6336 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 256 ms 4312 KB Output is correct
14 Correct 257 ms 3296 KB Output is correct
15 Correct 243 ms 4284 KB Output is correct
16 Correct 294 ms 4412 KB Output is correct
17 Correct 339 ms 18848 KB Output is correct
18 Correct 350 ms 23244 KB Output is correct
19 Correct 349 ms 23500 KB Output is correct
20 Correct 356 ms 23224 KB Output is correct
21 Correct 333 ms 23212 KB Output is correct
22 Correct 341 ms 23376 KB Output is correct
23 Correct 333 ms 23236 KB Output is correct
24 Correct 340 ms 23448 KB Output is correct
25 Correct 267 ms 20648 KB Output is correct
26 Correct 269 ms 20692 KB Output is correct
27 Correct 348 ms 22852 KB Output is correct
28 Correct 357 ms 23168 KB Output is correct
29 Correct 354 ms 22728 KB Output is correct
30 Correct 354 ms 22848 KB Output is correct
31 Correct 351 ms 23088 KB Output is correct
32 Correct 264 ms 19312 KB Output is correct
33 Correct 1 ms 204 KB Output is correct