oj.uz

Submission #47458

# Submission time Handle Problem Language Result Execution time Memory
47458 2018-05-03T09:27:04 Z mirbek01 Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 8508 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 2;

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

int main(){
      cin >> n >> q;

      int cn = 0;

      for(int i = 1; i <= n; i ++){
            cin >> d[i];
            if(d[i] == 1) cn ++;
      }

      if(cn == n){
            for(int i = 1; i <= q; i ++){
                  int t, l, r;
                  cin >> t >> l >> r;
                  int L = t - n, R = t;
                  if(l > R || L > r) {
                        cout << 0 << endl;
                        continue;
                  }
                  if(l <= L && R <= r){
                        cout << R - L + 1 << endl;
                        continue;
                  }
                  if(l <= L && L <= r){
                        cout << r - L + 1 << endl;
                        continue;
                  }
                  if(l <= R && R <= r){
                        cout << R - l + 1 << endl;
                        continue;
                  }
                  if(L <= l && r <= R){
                        cout << r - l + 1 << endl;
                        continue;
                  }
            }
            return 0;
      }

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

      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];
      }

      for(int i = 1; i <= q; i ++){
            int t, l, r;
            cin >> t >> l >> r;
            p[0] = t;
            int cnt = 0;
            if(p[0] >= l && p[0] <= r) cnt ++;
            for(int j = 1; j <= n; j ++){
                  p[j] = -j;
                  p[j] += (p[j - 1] - p[j] - 1) / d[j] * d[j];
                  if(p[j] >= l & p[j] <= r) cnt ++;
            }
            cout << cnt << endl;
      }
}
/**
3 1
2
5
3
4 2 4
**/

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:74:27: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
                   if(p[j] >= l & p[j] <= r) cnt ++;
                      ~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1646 ms 7180 KB Output is correct
2 Correct 1672 ms 7304 KB Output is correct
3 Correct 1687 ms 7380 KB Output is correct
4 Correct 1703 ms 7380 KB Output is correct
5 Correct 1893 ms 7380 KB Output is correct
6 Correct 1572 ms 7380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7380 KB Output is correct
2 Correct 29 ms 7380 KB Output is correct
3 Correct 28 ms 7380 KB Output is correct
4 Correct 28 ms 7380 KB Output is correct
5 Correct 28 ms 7380 KB Output is correct
6 Correct 31 ms 7380 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1646 ms 7180 KB Output is correct
2 Correct 1672 ms 7304 KB Output is correct
3 Correct 1687 ms 7380 KB Output is correct
4 Correct 1703 ms 7380 KB Output is correct
5 Correct 1893 ms 7380 KB Output is correct
6 Correct 1572 ms 7380 KB Output is correct
7 Correct 28 ms 7380 KB Output is correct
8 Correct 29 ms 7380 KB Output is correct
9 Correct 28 ms 7380 KB Output is correct
10 Correct 28 ms 7380 KB Output is correct
11 Correct 28 ms 7380 KB Output is correct
12 Correct 31 ms 7380 KB Output is correct
13 Execution timed out 2053 ms 8508 KB Time limit exceeded
14 Halted 0 ms 0 KB -