oj.uz

Submission #399923

# Submission time Handle Problem Language Result Execution time Memory
399923 2021-05-06T23:08:24 Z GioChkhaidze Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 2000 ms 8408 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], e[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;		
		}
	}
	
	int x = 1;
	for (int i = 0; i < v.size(); ++i) {
		e[i] = v[i].s;
		if (i) v[i].s += v[i - 1].s;
		v[i].f = x * ((d[v[i].f] - 1) / x + 1);
		x = v[i].f;
	}
	
	for (int i = v.size() - 2; i >= 0; --i) {
		v[i + 1].s = v[i].s;
	}
	v[0].s = 0;
	
	for (int i = 0; i < v.size(); ++i) {
		++v[i].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 - v[j].s - t % v[j].f;
			if (R < l) break;
			L = R - e[j] + 1;	
			if (R > r) R = r;
			if (L < l) L = l;
			if (L <= R) ans += R - L + 1;
		}
		
		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:45: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]
   45 |  for (int i = 0; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
worst_reporter3.cpp:58: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]
   58 |   for (int j = 0; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~
worst_reporter3.cpp:49:15: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
   49 |  int t, l, r, sum, ans, L, R;
      |               ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 5572 KB Output is correct
2 Correct 256 ms 5556 KB Output is correct
3 Correct 252 ms 5640 KB Output is correct
4 Correct 258 ms 5572 KB Output is correct
5 Correct 251 ms 5616 KB Output is correct
6 Correct 250 ms 5572 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 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 254 ms 5572 KB Output is correct
2 Correct 256 ms 5556 KB Output is correct
3 Correct 252 ms 5640 KB Output is correct
4 Correct 258 ms 5572 KB Output is correct
5 Correct 251 ms 5616 KB Output is correct
6 Correct 250 ms 5572 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 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 257 ms 3592 KB Output is correct
14 Correct 254 ms 3268 KB Output is correct
15 Correct 238 ms 3496 KB Output is correct
16 Correct 247 ms 3616 KB Output is correct
17 Execution timed out 2081 ms 8408 KB Time limit exceeded
18 Halted 0 ms 0 KB -