oj.uz

Submission #528886

# Submission time Handle Problem Language Result Execution time Memory
528886 2022-02-21T16:38:09 Z LucaDantas Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 488 ms 9264 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 5e5+10;

int d[maxn], qtd[maxn];

int main() {
	int n, q; scanf("%d %d", &n, &q);
	d[0] = 1;
	for(int i = 1; i <= n; i++)
		scanf("%d", d+i);

	vector<int> st; st.push_back(0);
	for(int i = 1; i <= n; i++) {
		if(d[st.back()] < d[i])
			st.push_back(i);
	}

	qtd[0] = 1;
	for(int i = 1; i < st.size(); i++) {
		int last = st[i-1], aq = st[i];
		qtd[st[i]] = ((d[st[i]] + qtd[st[i-1]] - 1) / qtd[st[i-1]]) * qtd[st[i-1]];
	}

	for(int i = 1; i <= n; i++)
		if(!qtd[i]) qtd[i] = qtd[i-1];

	/* for(int i = 0; i <= n; i++)
		printf("%d ", qtd[i]);
	puts(""); */

	for(int i = 0; i < q; i++) {
		int t, L, R; scanf("%d %d %d", &t, &L, &R);

		// printf("\ntempo %d\n", t);

		if(t < L) { puts("0"); continue; }

		int l = 0, r = n, GeqL = -1; // quero o primeiro cara maior ou igual a l
		while(l <= r) {
			int m = (l+r) >> 1;
			int pos = t - (t % qtd[m]) - m;
			if(pos >= L) GeqL = m, l = m+1;
			else r = m-1;
			// printf("%d -> %d\n", m, pos);
		}

		assert(GeqL != -1);

		if(t <= R) { printf("%d\n", GeqL+1); continue; }

		l = 0, r = n;
		int GR = 0;
		while(l <= r) {
			int m = (l+r) >> 1;
			int pos = t - (t % qtd[m]) - m;
			if(pos > R) GR = m, l = m+1;
			else r = m-1;
			// printf("%d -> %d\n", m, pos);
		}

		assert(GR != -1);

		// printf("%d %d\n", GeqL, GR);
		printf("%d\n", GeqL - GR);
	}
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 1; i < st.size(); i++) {
      |                 ~~^~~~~~~~~~~
worst_reporter3.cpp:22:7: warning: unused variable 'last' [-Wunused-variable]
   22 |   int last = st[i-1], aq = st[i];
      |       ^~~~
worst_reporter3.cpp:22:23: warning: unused variable 'aq' [-Wunused-variable]
   22 |   int last = st[i-1], aq = st[i];
      |                       ^~
worst_reporter3.cpp:9:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  int n, q; scanf("%d %d", &n, &q);
      |            ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d", d+i);
      |   ~~~~~^~~~~~~~~~~
worst_reporter3.cpp:34:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   int t, L, R; scanf("%d %d %d", &t, &L, &R);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 8172 KB Output is correct
2 Correct 484 ms 7432 KB Output is correct
3 Correct 486 ms 7464 KB Output is correct
4 Correct 482 ms 7368 KB Output is correct
5 Correct 471 ms 7356 KB Output is correct
6 Correct 488 ms 7484 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 316 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 8172 KB Output is correct
2 Correct 484 ms 7432 KB Output is correct
3 Correct 486 ms 7464 KB Output is correct
4 Correct 482 ms 7368 KB Output is correct
5 Correct 471 ms 7356 KB Output is correct
6 Correct 488 ms 7484 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 316 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Runtime error 58 ms 9264 KB Execution killed with signal 8
14 Halted 0 ms 0 KB -