Submission #47433

#	Time	Username	Problem	Language	Result	Execution time	Memory
47433		Talant	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	12 / 100	19 ms	12136 KiB

worst_reporter3

#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 (stderr)

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

• Subtask 1: 0 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81