oj.uz

Submission #128111

# Submission time Handle Problem Language Result Execution time Memory
128111 2019-07-10T12:33:44 Z RockyB Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 85676 KB 
#include <bits/stdc++.h>

#define int ll

#define f first
#define s second

#define pb push_back
#define pp pop_back

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

#define rep(a, b, c) for (int a = (b); (a) <= (c); ++a)
#define per(a, b, c) for (int a = (b); (a) >= (c); --a) 

#define nl '\n'
#define ioi exit(0);

using namespace std;

typedef long long ll;

const int MAX_N = (int)5e5 + 7;

int n, q;
int d[MAX_N], l[MAX_N], r[MAX_N], t[MAX_N], ans[MAX_N];

map <int, vector <int> > off;

int nxt[MAX_N], lst[MAX_N];
void prep() {
  int last = 1;
  rep(i, 1, n) {
    int df = (d[i] + last - 1) / last;
    lst[i] = df * last;
    last *= df;
  }
  per(i, n, 1) {
    if (lst[i] != lst[i + 1] || i == n) nxt[i] = i + 1;
    else nxt[i] = nxt[i + 1];
  }
}
vector < pair < pair <int, int>, ll > > a;
void solve(int T, vector <int> &qr) {
  int add = T, last = 1;
  a.clear();
  for (int i = 1, j = 0; i <= n; j = i + 1, i = nxt[i]) {
    int df = (d[i] + last - 1) / last;

    if (!sz(a)) a.pb({{0, i - 1}, i - 1});
    else a.pb({{j, i - 1}, {i - j}});
    a.pb({{i, i}, 1 + last * (add % df)});
    last *= df;
    add /= df;
    if (!add || nxt[i] > n) {
      if (i < n) a.pb({{i + 1, n}, {n - i}});
      break;
    }
  }
  for (auto it : qr) {
    int L = -1, R = -2;
    if (T >= l[it]) { // it's for right
      int ost = T - l[it];
      if (sz(a)) {
        R = min(ost, a[0].s);
      }
    }
    int sum = 0;
    rep(i, 0, sz(a) - 1) {
      sum += a[i].s;
      int val = T - sum;
      if (val >= l[it]) {
        R = a[i].f.s;
        
        int ost = val - l[it];
        if (i & 1 && i + 1 < sz(a)) {
          R += min(ost, a[i + 1].s);
        }
      }
      if (val <= r[it] && L == -1) {
        L = a[i].f.s;
        if (i % 2 == 0) {
          L -= max(0ll, min(r[it] - val, a[i].s - 1));
        }
      }
    }
    if (L != -1 && L <= R) ans[it] += R - L + 1;
  }
}
int32_t main() {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef IOI
    freopen ("in.txt", "r", stdin);
    freopen ("C.out", "w", stdout);
  #endif
  cin >> n >> q;
  d[0] = 1;
  rep(i, 1, n) {
    cin >> d[i];
  }
  rep(i, 1, q) {
    cin >> t[i] >> l[i] >> r[i];
    off[t[i]].pb(i);
  }
  prep();
  for (auto it : off) {
    solve(it.f, it.s);  
  }

  rep(i, 1, q) {
    cout << ans[i] << nl;
  }

  ioi
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 85496 KB Output is correct
2 Correct 1300 ms 85600 KB Output is correct
3 Correct 1310 ms 85676 KB Output is correct
4 Correct 1279 ms 85624 KB Output is correct
5 Correct 1289 ms 85628 KB Output is correct
6 Correct 1336 ms 85624 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 564 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 85496 KB Output is correct
2 Correct 1300 ms 85600 KB Output is correct
3 Correct 1310 ms 85676 KB Output is correct
4 Correct 1279 ms 85624 KB Output is correct
5 Correct 1289 ms 85628 KB Output is correct
6 Correct 1336 ms 85624 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 1319 ms 83504 KB Output is correct
14 Correct 1495 ms 83612 KB Output is correct
15 Correct 1364 ms 83700 KB Output is correct
16 Correct 1335 ms 83704 KB Output is correct
17 Correct 1725 ms 84992 KB Output is correct
18 Correct 1895 ms 85024 KB Output is correct
19 Correct 1789 ms 84916 KB Output is correct
20 Correct 1710 ms 85116 KB Output is correct
21 Execution timed out 2041 ms 85240 KB Time limit exceeded
22 Halted 0 ms 0 KB -