oj.uz

Submission #399913

# Submission time Handle Problem Language Result Execution time Memory
399913 2021-05-06T22:46:41 Z GioChkhaidze Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 2000 ms 11464 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;
	}
	
	if (v.size() > 60) {
		x += 1/0;
	}
	
	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:39:9: warning: division by zero [-Wdiv-by-zero]
   39 |   x += 1/0;
      |        ~^~
worst_reporter3.cpp:51: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]
   51 |   for (int j = 0; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 5900 KB Output is correct
2 Correct 276 ms 5940 KB Output is correct
3 Correct 260 ms 5864 KB Output is correct
4 Correct 267 ms 5840 KB Output is correct
5 Correct 259 ms 5868 KB Output is correct
6 Correct 256 ms 5844 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 2 ms 332 KB Output is correct
3 Correct 1 ms 336 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 266 ms 5900 KB Output is correct
2 Correct 276 ms 5940 KB Output is correct
3 Correct 260 ms 5864 KB Output is correct
4 Correct 267 ms 5840 KB Output is correct
5 Correct 259 ms 5868 KB Output is correct
6 Correct 256 ms 5844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 336 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 304 ms 3892 KB Output is correct
14 Correct 289 ms 3240 KB Output is correct
15 Correct 266 ms 3816 KB Output is correct
16 Correct 313 ms 3884 KB Output is correct
17 Execution timed out 2067 ms 11464 KB Time limit exceeded
18 Halted 0 ms 0 KB -