oj.uz

Submission #47434

# Submission time Handle Problem Language Result Execution time Memory
47434 2018-05-03T06:09:21 Z Talant Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 19 ms 11876 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],vec;

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

      v[0].push_front(0);
      vec.pb(0);

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

      if (n != cnt) {
            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) {
                  int pos = lower_bound(vec.begin(),vec.end(),l - t) - vec.begin();
                  int pos1 = upper_bound(vec.begin(),vec.end(),r - t) - vec.begin() - 1;

                  cout << (pos1 - pos + 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 3704 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 16 ms 11748 KB Output is correct
2 Correct 17 ms 11824 KB Output is correct
3 Correct 17 ms 11864 KB Output is correct
4 Correct 19 ms 11864 KB Output is correct
5 Correct 17 ms 11876 KB Output is correct
6 Correct 17 ms 11876 KB Output is correct

Subtask #3
0 / 81.0

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