oj.uz

Submission #47435

# Submission time Handle Problem Language Result Execution time Memory
47435 2018-05-03T06:11:23 Z mirbek01 Worst Reporter 3 (JOI18_worst_reporter3) C++17
0 / 100
 2000 ms 9336 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 2;

long long n, q, d[N], p[N];

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

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

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

      for(int i = 1; i <= q; i ++){
            int t, l, r;
            scanf("%d %d %d", &t, &l, &r);
            p[0] = t;
            for(int j = 1; j <= n; j ++){
                  p[j] = -j;
                  int lo = 0, hi = 1000;
                  while(hi - lo > 1){
                        int md = (lo + hi) >> 1;
                        if(md * d[j] + p[j] < p[j - 1])
                              lo = md;
                        else
                              hi = md;
                  }
                  if(hi * d[j] + p[j] < p[j - 1]) lo = hi;
                  p[j] = lo * d[j] + p[j];
            }
            int cn = 0;
            for(int j = 0; j <= n; j ++)
                  if(l <= p[j] && p[j] <= r) cn ++;
            printf("%d\n", cn);
      }
}
/**
3 6
2
5
3
6 2 4
**/

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:10:28: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
       scanf("%d %d", &n, &q);
                      ~~    ^
worst_reporter3.cpp:10:28: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
worst_reporter3.cpp:13:30: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
             scanf("%d", &d[i]);
                         ~~~~~^
worst_reporter3.cpp:10:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &q);
       ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:13:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &d[i]);
             ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:30: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 9336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9336 KB Output is correct
2 Correct 51 ms 9336 KB Output is correct
3 Correct 45 ms 9336 KB Output is correct
4 Correct 47 ms 9336 KB Output is correct
5 Incorrect 51 ms 9336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 9336 KB Time limit exceeded
2 Halted 0 ms 0 KB -