oj.uz

Submission #399910

# Submission time Handle Problem Language Result Execution time Memory
399910 2021-05-06T22:45:22 Z GioChkhaidze Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 2000 ms 20788 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;
	}
	
	for (int i = 1; i <= q; ++i) {
		int t, l, r;
		cin >> t >> l >> r;
		if (t < l) {
			cout << 0 << "\n";
			continue;
		}
		
		int sum = -1, ans = (l <= t && t <= r);
		for (int j = 0; j < v.size(); ++j) {
			int R = t + (sum - t % v[j].f);
			int L = R - v[j].s + 1;	
			ans += max(0, min(R, r) - max(L, 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 272 ms 20788 KB Output is correct
2 Correct 263 ms 20668 KB Output is correct
3 Correct 301 ms 20696 KB Output is correct
4 Correct 262 ms 20676 KB Output is correct
5 Correct 265 ms 20676 KB Output is correct
6 Correct 265 ms 20680 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 20788 KB Output is correct
2 Correct 263 ms 20668 KB Output is correct
3 Correct 301 ms 20696 KB Output is correct
4 Correct 262 ms 20676 KB Output is correct
5 Correct 265 ms 20676 KB Output is correct
6 Correct 265 ms 20680 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct
13 Correct 291 ms 19148 KB Output is correct
14 Correct 298 ms 19776 KB Output is correct
15 Correct 303 ms 18496 KB Output is correct
16 Correct 296 ms 19016 KB Output is correct
17 Execution timed out 2062 ms 11456 KB Time limit exceeded
18 Halted 0 ms 0 KB -