oj.uz

Submission #47457

# Submission time Handle Problem Language Result Execution time Memory
47457 2018-05-03T09:27:02 Z Talant Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 2000 ms 11272 KB 
#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 = inf;
                  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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1848 ms 11272 KB Output is correct
2 Execution timed out 2039 ms 11272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1848 ms 11272 KB Output is correct
2 Execution timed out 2039 ms 11272 KB Time limit exceeded
3 Halted 0 ms 0 KB -