Submission #47460

#	Time	Username	Problem	Language	Result	Execution time	Memory
47460		Talant	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1751 ms	95980 KiB

worst_reporter3

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)6e5 + 7;

int n,q,d[N],a[N];
int t,L,R;
int cnt;

bool check (int x) {
      int o = floor(t / a[x]) * a[x] - x;
      if (L <= o)
            return true;
      return false;
}
bool f(int x) {
      int o = floor(t / a[x]) * a[x] - x;
      if (R >= o)
            return true;
      return false;
}
main () {
      scanf ("%lld%lld", &n,&q);

      for (int i = 1; i <= n; i ++)
            scanf ("%lld", &d[i]);

      for (int i = 1; i <= n; i ++) {
            if (i == 1)
                  a[i] = d[i];
            else {
                  int l = 1,r = a[i - 1] + d[i] + 5;
                  while (r - l > 1) {
                        int m = (r + l) >> 1;
                        int o = floor(m / a[i - 1]) * a[i - 1] - (i - 1);
                        if (o >= d[i] + 1 + (-i))
                              r = m;
                        else
                              l = m;
                  }
                  int o = floor(l / a[i - 1]) * a[i - 1] - (i - 1);
                  if (o >= d[i] + 1 + (-i))
                              r = l;
                  a[i] = r;
            }
      }
      while (q --) {
            scanf ("%lld%lld%lld", &t,&L,&R);

            if (t < L) {
                  puts("0");
                  continue;
            }
            int l = 1,r = n;

            while (r - l > 1) {
                  int m = (r + l) >> 1;
                  if (check(m))
                        l = m;
                  else
                        r = m;
            }
            if (check(r))
                  l = r;
            if (!check(l))
                  l = 0;

            if (l == 0 && t <= R) {
                  puts("1");
                  continue;
            }
            if (l == 0) {
                  puts("0");
                  continue;
            }
            int lo = 1,hi = l;

            while (hi - lo > 1) {
                  int m = (hi + lo) >> 1;
                  if (f(m))
                        hi = m;
                  else
                        lo = m;
            }
            if (!f(hi)) {
                  puts("0");
                  continue;
            }
            if (f(lo))
                  hi = lo;

            if (L <= t && t <= R)
                  printf("%lld\n", l - hi + 2);
            else
                  printf("%lld\n", l - hi + 1);
      }
}

Compilation message (stderr)

worst_reporter3.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:33:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf ("%lld%lld", &n,&q);
       ~~~~~~^~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:36:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%lld", &d[i]);
             ~~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:58:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%lld%lld%lld", &t,&L,&R);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81