Submission #963778

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963778	2024-04-15T16:21:47 Z	abczz	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1469 ms	33172 KB

worst_reporter3

#include <iostream>
#define ll long long

using namespace std;

ll n, q, t, ql, qr, l, r, ul, ur, mid, A[500001], D[500001], T[500001];
int main() {
  cin >> n >> q;
  for (int i=1; i<=n; ++i) cin >> A[i];
  T[0] = D[0] = 1;
  for (int i=1; i<=n; ++i) {
    T[i] = T[i-1] * (ll)((A[i]+D[i-1]-1)/D[i-1]);
    D[i] = (ll)((A[i]+D[i-1]-1)/D[i-1]) * D[i-1];
  }
  while (q--) {
    cin >> t >> ql >> qr;
    l = 0, r = n;
    while (l < r) {
      mid = (l+r+1)/2;
      if (ql <= (ll)(t/T[mid]) * D[mid] - mid) l = mid;
      else r = mid-1;
    }
    ur = l;
    l = 0, r = n;
    while (l < r) {
      mid = (l+r)/2;
      if ((ll)(t/T[mid]) * D[mid] - mid <= qr) r = mid;
      else l = mid+1;
    }
    ul = l;
    if (ql <= (ll)(t/T[ur]) * D[ur] - ur && (ll)(t/T[ul]) * D[ul] - ul <= qr) cout << ur-ul+1 << '\n';
    else cout << "0\n";
  }
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1425 ms	30480 KB	Output is correct
2	Correct	1435 ms	30648 KB	Output is correct
3	Correct	1469 ms	30540 KB	Output is correct
4	Correct	1433 ms	30480 KB	Output is correct
5	Correct	1386 ms	30472 KB	Output is correct
6	Correct	1430 ms	30508 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4812 KB	Output is correct
2	Correct	3 ms	4696 KB	Output is correct
3	Correct	4 ms	4440 KB	Output is correct
4	Correct	3 ms	4444 KB	Output is correct
5	Correct	3 ms	4444 KB	Output is correct
6	Correct	3 ms	4444 KB	Output is correct

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1425 ms	30480 KB	Output is correct
2	Correct	1435 ms	30648 KB	Output is correct
3	Correct	1469 ms	30540 KB	Output is correct
4	Correct	1433 ms	30480 KB	Output is correct
5	Correct	1386 ms	30472 KB	Output is correct
6	Correct	1430 ms	30508 KB	Output is correct
7	Correct	4 ms	4812 KB	Output is correct
8	Correct	3 ms	4696 KB	Output is correct
9	Correct	4 ms	4440 KB	Output is correct
10	Correct	3 ms	4444 KB	Output is correct
11	Correct	3 ms	4444 KB	Output is correct
12	Correct	3 ms	4444 KB	Output is correct
13	Correct	1203 ms	29076 KB	Output is correct
14	Correct	1194 ms	29680 KB	Output is correct
15	Correct	1149 ms	28624 KB	Output is correct
16	Correct	1157 ms	28928 KB	Output is correct
17	Correct	1324 ms	32988 KB	Output is correct
18	Correct	1272 ms	32964 KB	Output is correct
19	Correct	1343 ms	33116 KB	Output is correct
20	Correct	1294 ms	33148 KB	Output is correct
21	Correct	1344 ms	32968 KB	Output is correct
22	Correct	1325 ms	33172 KB	Output is correct
23	Correct	1341 ms	32984 KB	Output is correct
24	Correct	1307 ms	33148 KB	Output is correct
25	Correct	1414 ms	30560 KB	Output is correct
26	Correct	1367 ms	30628 KB	Output is correct
27	Correct	1360 ms	32668 KB	Output is correct
28	Correct	1333 ms	33052 KB	Output is correct
29	Correct	1292 ms	32872 KB	Output is correct
30	Correct	1347 ms	32876 KB	Output is correct
31	Correct	1393 ms	32708 KB	Output is correct
32	Correct	1285 ms	29336 KB	Output is correct
33	Correct	1 ms	4440 KB	Output is correct