oj.uz

Submission #47466

# Submission time Handle Problem Language Result Execution time Memory
47466 2018-05-03T10:13:24 Z mirbek01 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1519 ms 15500 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 2;

long long n, q, d[N], p[N], ti[N], inf = 2e9;

int main(){
      scanf("%lld %lld", &n, &q);

      int cn = 0;

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

      for(int i = 1; i <= n; i ++){
            p[i] = -i;
      }

      ti[0] = 1;
      d[0] = 1;
      ti[1] = d[1];

      for(int i = 2; i <= n; i ++){
            int lo = 0, hi = 1e9;
            while(hi - lo > 1){
                  int md = (lo + hi) >> 1;
                  if((p[i - 1] + d[i - 1] * md - p[i]) > d[i])
                        hi = md;
                  else
                        lo = md;
            }
            if((p[i - 1] + d[i - 1] * lo - p[i]) > d[i]) hi = lo;
            d[i] = p[i - 1] + d[i - 1] * hi - 1 - p[i];
            ti[i] = min(hi * ti[i - 1], inf);
      }

      for(int i = 1; i <= q; i ++){
            int t, l, r;
            scanf("%d %d %d", &t, &l, &r);
            int L, R;
            int lo = 0, hi = n;
            while(hi - lo > 1){
                  int md = (lo + hi) >> 1;
                  if(t / ti[md] * d[md] + p[md] >= l)
                        lo = md;
                  else
                        hi = md;
            }

            if(t / ti[hi] * d[hi] + p[hi] >= l) lo = hi;
            if(t / ti[lo] * d[lo] + p[lo] < l) {
                  puts("0");
                  continue;
            }

            R = lo;

            lo = 0, hi = n;

            while(hi - lo > 1){
                  int md = (lo + hi) >> 1;
                  if(t / ti[md] * d[md] + p[md] <= r)
                        hi = md;
                  else
                        lo = md;
            }

            if(t / ti[lo] * d[lo] + p[lo] <= r) hi = lo;
            if(t / ti[hi] * d[hi] + p[hi] > r) {
                  puts("0");
                  continue;
            }

            L = hi;

            printf("%d\n", R - L + 1);
      }
}
/**
3 1
2
5
3
2 2 4
**/

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:10:12: 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:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &d[i]);
             ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &t, &l, &r);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 14984 KB Output is correct
2 Correct 1463 ms 15232 KB Output is correct
3 Correct 1449 ms 15232 KB Output is correct
4 Correct 1452 ms 15232 KB Output is correct
5 Correct 1457 ms 15232 KB Output is correct
6 Correct 1442 ms 15232 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 14984 KB Output is correct
2 Correct 1463 ms 15232 KB Output is correct
3 Correct 1449 ms 15232 KB Output is correct
4 Correct 1452 ms 15232 KB Output is correct
5 Correct 1457 ms 15232 KB Output is correct
6 Correct 1442 ms 15232 KB Output is correct
7 Correct 3 ms 15232 KB Output is correct
8 Correct 4 ms 15232 KB Output is correct
9 Correct 3 ms 15232 KB Output is correct
10 Correct 3 ms 15232 KB Output is correct
11 Correct 3 ms 15232 KB Output is correct
12 Correct 3 ms 15232 KB Output is correct
13 Correct 944 ms 15232 KB Output is correct
14 Correct 1002 ms 15232 KB Output is correct
15 Correct 863 ms 15232 KB Output is correct
16 Correct 956 ms 15232 KB Output is correct
17 Correct 1111 ms 15232 KB Output is correct
18 Correct 1110 ms 15232 KB Output is correct
19 Correct 1097 ms 15232 KB Output is correct
20 Correct 1101 ms 15232 KB Output is correct
21 Correct 1100 ms 15232 KB Output is correct
22 Correct 1086 ms 15232 KB Output is correct
23 Correct 1113 ms 15232 KB Output is correct
24 Correct 1120 ms 15232 KB Output is correct
25 Correct 1492 ms 15500 KB Output is correct
26 Correct 1519 ms 15500 KB Output is correct
27 Correct 1286 ms 15500 KB Output is correct
28 Correct 1224 ms 15500 KB Output is correct
29 Correct 1114 ms 15500 KB Output is correct
30 Correct 1262 ms 15500 KB Output is correct
31 Correct 1224 ms 15500 KB Output is correct
32 Correct 1159 ms 15500 KB Output is correct
33 Correct 3 ms 15500 KB Output is correct