Submission #782271

#	Time	Username	Problem	Language	Result	Execution time	Memory
782271		tvladm2009	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	461 ms	29336 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 5e5 + 7;
const int INF = (int) 1e9;
int a[N], d[N], when[N], jump[N], p[N];
int n, q;

int calc(int t, int x) {
  return -x + (t / when[x]) * when[x];
}

int get(int t, int x) {
  int low = 1, high = n, sol = n + 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (calc(t, mid) <= x) {
      high = mid - 1;
      sol = mid;
    } else {
      low = mid + 1;
    }
  }
  return n - sol + 1;
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> d[i];
  }
  for (int i = 1; i <= n; i++) {
    a[i] = -i;
  }
  when[1] = d[1];
  jump[1] = d[1];
  for (int i = 2; i <= n; i++) {
    int from = -i + d[i] + 1 + (i - 1);
    assert(jump[i - 1] != 0);
    int moment = (from - 1) / jump[i - 1] + 1;
    int t = when[i - 1] * moment;
    when[i] = t;
    jump[i] = a[i - 1] + jump[i - 1] * (when[i] / when[i - 1]) - a[i] - 1;
  }

  for (int i = 1; i <= n; i++) {
    assert(when[i] == jump[i]);
  }
  for (int i = 1; i < n; i++) {
    assert(when[i] <= when[i + 1]);
  }

  for (int i = 1; i <= q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    cout << get(t, r) - get(t, l - 1) + (l <= t && t <= r) << "\n";
  }
  return 0;
}

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