oj.uz

Submission #779813

# Submission time Handle Problem Language Result Execution time Memory
779813 2023-07-11T23:03:30 Z tvladm2009 Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 66 ms 28236 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

vector<T> questions[N];
int sol[N];

int smaller(int x) {
  int low = 1, high = n, sol = 0;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] <= x) {
      low = mid + 1;
      sol = mid;
    } else {
      high = mid - 1;
    }
  }
  return sol;
}

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];
  }
  int mxt = 0;
  for (int i = 1; i <= q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    mxt = max(mxt, t);
    questions[t].push_back({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 <= mxt; i++) {
    for (int j = 1; j <= n; j++) {
      p[j] = j;
    }
    sort(p + 1, p + n + 1, [&](int x, int y) {
      return -x + (i / when[x]) * jump[x] < -y + (i / when[y]) * jump[y];
    });
    for (int j = 1; j <= n; j++) {
      a[j] = -p[j] + (i / when[p[j]]) * jump[p[j]];
    }
    for (auto &it : questions[i]) {
      int l = it.l;
      int r = it.r;
      int ret = 0;
      ret = smaller(r) - smaller(l - 1);
      ret += (l <= i && i <= r);
      sol[it.id] = ret;
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << sol[i] << "\n";
  }
  return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 28236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12088 KB Output is correct
2 Correct 64 ms 12116 KB Output is correct
3 Correct 64 ms 12116 KB Output is correct
4 Correct 65 ms 12140 KB Output is correct
5 Correct 66 ms 12144 KB Output is correct
6 Correct 65 ms 12160 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 28236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -