oj.uz

Submission #774885

# Submission time Handle Problem Language Result Execution time Memory
774885 2023-07-06T04:54:36 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 472 ms 7212 KB 
#include <bits/stdc++.h>
using namespace std;

// Write down the limits of the problem here

int main() {
	// Try to avoid cin, cout :)

	int tc = 1; // scanf("%d", &tc);
	while(tc--) {
		/// Your solution here
	    int n, q;
        scanf("%d%d", &n, &q);
        vector<int> d(n + 1);
        for (int i = 1; i <= n ; i++) scanf("%d", &d[i]);
        vector<int> f(n + 1);
        f[0] = 1;
        d[0] = 1;
        for (int i = 1; i <= n; i++){
            f[i] = int(ceil(d[i]/double(f[i - 1])))*f[i - 1];
        }
	    while(q--){
            int t, l, r;
            scanf("%d%d%d", &t, &l, &r);
            int L = 0;
            int R = n;
            while(L <= R){
                int m = (L + R) >> 1;
                int T = (t/f[m])*f[m] - m;
                if (T < l) R = m - 1;
                else L = m + 1;
            }
            int firstpos = L;
            L = 0, R = n;
            while( L <= R){
                int m  = (L + R )>> 1;
                int T = (t/f[m])*f[m] - m;
                if (T > r) L = m + 1;
                else R = m - 1;
            }
            int lastpos = R;
            printf("%d\n", max(0, firstpos - lastpos - 1));
        }
    }
	return 0;
}

/*
 * Ermm don't underestimate Div2A, pls...
 * 
 * IMPORTANT:: If there isn't a clear-cut approach for your program, DO NOT CODE YET!
 * 
 * Analyze the time complexity and space complexity even if it *seems* efficient
 *
 * Write down some notes for more complicated problems
 * 
 * Also, please, CP isn't supposed to be complicated
 * 
**/

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d%d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~
worst_reporter3.cpp:15:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         for (int i = 1; i <= n ; i++) scanf("%d", &d[i]);
      |                                       ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |             scanf("%d%d%d", &t, &l, &r);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 7168 KB Output is correct
2 Correct 458 ms 7200 KB Output is correct
3 Correct 452 ms 7180 KB Output is correct
4 Correct 468 ms 7180 KB Output is correct
5 Correct 456 ms 7132 KB Output is correct
6 Correct 466 ms 7164 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 7168 KB Output is correct
2 Correct 458 ms 7200 KB Output is correct
3 Correct 452 ms 7180 KB Output is correct
4 Correct 468 ms 7180 KB Output is correct
5 Correct 456 ms 7132 KB Output is correct
6 Correct 466 ms 7164 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 282 ms 5200 KB Output is correct
14 Correct 281 ms 5112 KB Output is correct
15 Correct 277 ms 5116 KB Output is correct
16 Correct 279 ms 5132 KB Output is correct
17 Correct 366 ms 6628 KB Output is correct
18 Correct 356 ms 6616 KB Output is correct
19 Correct 345 ms 6548 KB Output is correct
20 Correct 340 ms 6592 KB Output is correct
21 Correct 338 ms 6564 KB Output is correct
22 Correct 351 ms 6544 KB Output is correct
23 Correct 356 ms 6600 KB Output is correct
24 Correct 342 ms 6744 KB Output is correct
25 Correct 456 ms 7140 KB Output is correct
26 Correct 456 ms 7212 KB Output is correct
27 Correct 380 ms 7000 KB Output is correct
28 Correct 382 ms 6936 KB Output is correct
29 Correct 380 ms 7056 KB Output is correct
30 Correct 373 ms 6968 KB Output is correct
31 Correct 389 ms 6972 KB Output is correct
32 Correct 370 ms 6676 KB Output is correct
33 Correct 0 ms 212 KB Output is correct