Submission #47434

#	Time	Username	Problem	Language	Result	Execution time	Memory
47434		Talant	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	12 / 100	19 ms	11876 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],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 (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