oj.uz

Submission #128122

# Submission time Handle Problem Language Result Execution time Memory
128122 2019-07-10T12:44:37 Z RockyB Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 85800 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];
  }
}

pair < pair <int, int>, ll> a[MAX_N];
void solve(int T, vector <int> &qr) {
  int add = T;
  int sz = 0;
  int last = 1;
  for (int i = 1, j = 0; i <= n; j = i + 1, i = nxt[i]) {
    int df = (d[i] + last - 1) / last;
 
    if (!sz) a[sz++] = {{0, i - 1}, i - 1};
    else a[sz++] = {{j, i - 1}, {i - j}};
    a[sz++] = {{i, i}, 1 + last * (add % df)};
    last *= df;
    add /= df;
    if (!add || nxt[i] > n) {
      if (i < n) a[sz++] = {{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) {
        R = min(ost, a[0].s);
      }
    }
    int sum = 0;
    rep(i, 0, sz - 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) {
          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() {
  #ifdef IOI
    freopen ("in.txt", "r", stdin);
    freopen ("C.out", "w", stdout);
  #endif
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  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 1415 ms 85584 KB Output is correct
2 Correct 1445 ms 85760 KB Output is correct
3 Correct 1303 ms 85676 KB Output is correct
4 Correct 1403 ms 85576 KB Output is correct
5 Correct 1303 ms 85752 KB Output is correct
6 Correct 1310 ms 85620 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 4 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 1415 ms 85584 KB Output is correct
2 Correct 1445 ms 85760 KB Output is correct
3 Correct 1303 ms 85676 KB Output is correct
4 Correct 1403 ms 85576 KB Output is correct
5 Correct 1303 ms 85752 KB Output is correct
6 Correct 1310 ms 85620 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 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 1317 ms 83500 KB Output is correct
14 Correct 1346 ms 83576 KB Output is correct
15 Correct 1325 ms 83576 KB Output is correct
16 Correct 1323 ms 83704 KB Output is correct
17 Correct 1691 ms 85244 KB Output is correct
18 Correct 1654 ms 85240 KB Output is correct
19 Correct 1703 ms 84996 KB Output is correct
20 Correct 1799 ms 85100 KB Output is correct
21 Correct 1799 ms 85008 KB Output is correct
22 Correct 1910 ms 85020 KB Output is correct
23 Correct 1700 ms 85112 KB Output is correct
24 Correct 1656 ms 84960 KB Output is correct
25 Correct 1329 ms 85624 KB Output is correct
26 Correct 1335 ms 85800 KB Output is correct
27 Correct 1695 ms 85420 KB Output is correct
28 Correct 1760 ms 85328 KB Output is correct
29 Correct 1738 ms 85496 KB Output is correct
30 Correct 1794 ms 85508 KB Output is correct
31 Execution timed out 2073 ms 85508 KB Time limit exceeded
32 Halted 0 ms 0 KB -