Submission #779817

#	Time	Username	Problem	Language	Result	Execution time	Memory
779817		tvladm2009	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	0 / 100	2045 ms	66656 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
const int N = (int) 5e5 + 7;
int d[N], a[N], when[N], jump[N];
pair<int, int> aux[N];
int n, q;

struct T {
  int t;
  int l;
  int r;
  int id;
};

vector<T> questions;
int sol[N];
oset<pair<int, int>> s;

void baga(int x) {
  s.erase({a[x], x});
  a[x] += jump[x];
  s.insert({a[x], x});
}

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 <= q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    questions.push_back({t, l, r, 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++) {
    s.insert({a[i], i});
  }
  questions.push_back({0, 1, n, 0});
  sort(questions.begin(), questions.end(), [&](T a, T b) {
    return a.t < b.t;
  });
  q++;
  for (int i = 1; i <= n; i++) {
    aux[i] = {when[i], i};
  }
  sort(aux + 1, aux + n + 1);
  for (int i = 1; i < q; i++) {
    int j = 1;
    while (j <= n && aux[j].first <= questions[i].t - questions[i - 1].t) {
      baga(aux[j].second);
      j++;
    }
    int steps = 50;
    while (j <= n && steps > 0) {
      if (questions[i - 1].t + when[j] - questions[i - 1].t % when[j] <= questions[i].t) {
        baga(aux[j].second);
      }
      j++;
      steps--;
    }
    int l = questions[i].l;
    int r = questions[i].r;
    int ret = s.order_of_key(make_pair(r, n + 1)) - s.order_of_key(make_pair(l - 1, n + 1));
    sol[questions[i].id] = ret + (l <= i && i <= r);
  }
  for (int i = 1; i <= q - 1; i++) {
    cout << sol[i] << "\n";
  }
  return 0;
}

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