oj.uz

Submission #399918

# Submission time Handle Problem Language Result Execution time Memory
399918 2021-05-06T22:55:49 Z GioChkhaidze Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 2000 ms 6468 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];
	}
	
	for (int i = 1; i <= n; ++i) {
		if (!v.size() || d[v.back().f] < d[i]) {
			v.pb({i, 1});
		}
			else {
			++v.back().s;		
		}
	}
	
	ll x = 1;
	for (int i = 0; i < v.size(); ++i) {
		v[i].f = x * ((d[v[i].f] - 1) / x + 1);
		x = v[i].f;
	}
	
	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:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
worst_reporter3.cpp:47: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]
   47 |   for (int j = 0; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 5188 KB Output is correct
2 Correct 306 ms 5316 KB Output is correct
3 Correct 262 ms 5160 KB Output is correct
4 Correct 272 ms 5188 KB Output is correct
5 Correct 257 ms 5188 KB Output is correct
6 Correct 257 ms 5248 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 5188 KB Output is correct
2 Correct 306 ms 5316 KB Output is correct
3 Correct 262 ms 5160 KB Output is correct
4 Correct 272 ms 5188 KB Output is correct
5 Correct 257 ms 5188 KB Output is correct
6 Correct 257 ms 5248 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 269 ms 3228 KB Output is correct
14 Correct 263 ms 3212 KB Output is correct
15 Correct 246 ms 3176 KB Output is correct
16 Correct 281 ms 3140 KB Output is correct
17 Execution timed out 2073 ms 6468 KB Time limit exceeded
18 Halted 0 ms 0 KB -