Submission #774885

#	Time	Username	Problem	Language	Result	Execution time	Memory
774885		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	472 ms	7212 KiB

worst_reporter3

#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 (stderr)

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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81