oj.uz

Submission #47433

# Submission time Handle Problem Language Result Execution time Memory
47433 2018-05-03T06:05:05 Z Talant Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 19 ms 12136 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)4200;

int n,q,d[N],a[N];
int t,l,r;
int cnt;

deque <int> v[N];

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

      v[0].push_front(0);

      for (int i = 1; i <= n; i ++) {
            cin >> d[i];
            if (d[i] == 1)
                  cnt ++;
            a[i] = -i;
      }
      d[0] = 1;

      for (int i = 1; i <= 1000; i ++) {
            for (int j = 0; j <= n; j ++) {
                  if (j == 0)
                        a[j] ++,v[i].push_front(a[j]);
                  else {
                        if (a[j] + d[j] + 1 <= a[j - 1])
                              a[j] = a[j - 1] - 1;
                        v[i].push_front(a[j]);
                  }
            }
      }
      while (q --) {
            cin >> t >> l >> r;
            if (cnt == n) {
                  if (t - n > r)
                        cout << 0 << endl;
                  else
                        cout << max(0ll,min(n,min(t,r) - max(l,t - n) + 1)) << endl;
                  continue;
            }
            int pos = lower_bound(v[t].begin(),v[t].end(),l) - v[t].begin();
            int pos1 = upper_bound(v[t].begin(),v[t].end(),r) - v[t].begin() - 1;

            cout << (pos1 - pos + 1) << endl;
      }
}

Compilation message

worst_reporter3.cpp:22:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11804 KB Output is correct
2 Correct 18 ms 11884 KB Output is correct
3 Correct 18 ms 11916 KB Output is correct
4 Correct 18 ms 12136 KB Output is correct
5 Correct 19 ms 12136 KB Output is correct
6 Correct 18 ms 12136 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -