oj.uz

Submission #47453

# Submission time Handle Problem Language Result Execution time Memory
47453 2018-05-03T09:01:32 Z mirbek01 Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 1950 ms 22576 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 2;

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

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 || n > 1e3){
            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 = 0; i <= 1000; i ++){
            if(i == 0){
                  for(int j = 1; j <= n; j ++)
                        p[i][j] = -j;
            } else {
                  p[i][0] = i;
                  for(int j = 1; j <= n; j ++){
                        p[i][j] = p[i - 1][j];
                        if(p[i][j - 1] - p[i][j] > d[j])
                              p[i][j] = p[i][j - 1] - 1;
                  }
            }
      }

      for(int i = 1; i <= q; i ++){
            int t, l, r;
            cin >> t >> l >> r;
            int cn = 0;
            for(int j = 0; j <= n; j ++){
                  if(p[t][j] >= l && p[t][j] <= r) cn ++;
            }
            cout << cn << endl;
      }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 7284 KB Output is correct
2 Correct 1757 ms 7380 KB Output is correct
3 Correct 1778 ms 7388 KB Output is correct
4 Correct 1831 ms 7388 KB Output is correct
5 Correct 1720 ms 7636 KB Output is correct
6 Correct 1689 ms 7636 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8340 KB Output is correct
2 Correct 12 ms 8468 KB Output is correct
3 Correct 12 ms 8468 KB Output is correct
4 Correct 12 ms 8468 KB Output is correct
5 Correct 12 ms 8484 KB Output is correct
6 Correct 12 ms 8492 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 7284 KB Output is correct
2 Correct 1757 ms 7380 KB Output is correct
3 Correct 1778 ms 7388 KB Output is correct
4 Correct 1831 ms 7388 KB Output is correct
5 Correct 1720 ms 7636 KB Output is correct
6 Correct 1689 ms 7636 KB Output is correct
7 Correct 12 ms 8340 KB Output is correct
8 Correct 12 ms 8468 KB Output is correct
9 Correct 12 ms 8468 KB Output is correct
10 Correct 12 ms 8468 KB Output is correct
11 Correct 12 ms 8484 KB Output is correct
12 Correct 12 ms 8492 KB Output is correct
13 Incorrect 1950 ms 22576 KB Output isn't correct
14 Halted 0 ms 0 KB -