oj.uz

Submission #128105

# Submission time Handle Problem Language Result Execution time Memory
128105 2019-07-10T12:30:59 Z RockyB Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1706 ms 78880 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];

unordered_map <int, vector <int> > off;

struct fenwick {
  pair <ll, int> f[MAX_N];

  void upd(int p, ll df, int t) {
    for (; p < MAX_N; p |= p + 1) {
      f[p].f += df;
      f[p].s += t;
    }
  }
  pair <ll, int> get(int p) {
    pair <ll, int> res = {0, 0};
    for (; p >= 0; p = (p & (p + 1)) - 1) {
      res.f += f[p].f;
      res.s += f[p].s;
    }
    return res;
  }
} F; 

pair <int, int> inter(pair <int, int> x, pair <int, int> y) {
  return {max(x.f, y.f), min(x.s, y.s)};
}
ll get_val(int p, int T) {
  pair <ll, int> cur = F.get(p);
  //cerr << cur.f << ' ' << T << nl;
  int one = p - cur.s; 
/*   if (S != -1) {
    pair <int, int> rng = inter({1, p}, {S, E});
    if (rng.f <= rng.s) {
      // cerr << cur.f << ' ' << one << nl;
      one -= pref[rng.s].s - pref[rng.f - 1].s;
      cur.f += pref[rng.s].f - pref[rng.f - 1].f;
    }
  }
 */
  return T - (cur.f + one);
}

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];
  }
}
void solve(int T, vector <int> &qr) {
  int add = T;
  vector < pair < pair <int, int>, ll > > a;
  int last = 1;
  /* rep(i, 1, n) cerr << lst[i] << ' ';
  cerr << nl; */
  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)});
    //F.upd(i, 1 + last * (add % df), 1);   
    //cerr << 1 + last * (add % df) << ' ' << i << nl;
    //sum += 1 + last * (add % df);

    last *= df;
    add /= df;
    if (!add || nxt[i] > n) {
      if (i < n) a.pb({{i + 1, n}, {n - i}});
      break;
    }
  }
  /* last = 1;
  cerr << nl;
  add = T;
  for (int i = 1; i <= n; i++) {
    int df = (d[i] + last - 1) / last;
    cerr << 1 + last * (add % df) << ' ' << i << ' ' << last * df << nl;
    //sum += 1 + last * (add % df);

    last *= df;
    add /= df;
  } */

  /* for (auto it : a) {
    cerr << it.f.f << ' ' << it.f.s << ' ' << it.s << nl;
  } */

  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;
      // cerr << val << ' ' << a[i].f.f << ' ' << a[i].f.s << ' ' << r[it] << nl;
      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) {
//          cerr << "DA";
          // cerr << L << "<-\n";
          L -= max(0ll, min(r[it] - val, a[i].s - 1));
//          cerr << L << "<-\n";
        }
      }
    }
    /* cerr << nl;
    cerr << L << ' ' << R << nl; */
    
    /*
    int lo = 1, hi = n;
    while (lo <= hi) {
      int mid = lo + hi >> 1;
      if (get_val(mid, T) >= l[it]) L = mid, lo = mid + 1;
      else hi = mid - 1;
    }
    lo = 1, hi = n;
    while (lo <= hi) {
      int mid = lo + hi >> 1;
      if (get_val(mid, T) <= r[it]) R = mid, hi = mid - 1;
      else lo = mid + 1;
    }*/
    //cerr << R << ' ' << L << nl;
    if (L != -1 && L <= R) ans[it] += R - L + 1;

    //if (l[it] <= T && T <= r[it]) ans[it]++;

    // cerr << ans[it] << nl; 
    //ans[it] = upper_bound(all(a), r[it]) - lower_bound(all(a), l[it]);
  }

  // cout << ans[2] << nl;
  /* for (auto it : del) {
    F.upd(it.f, -it.s, -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();
  /* solve(4, off[4]);
  ioi */
  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 938 ms 78524 KB Output is correct
2 Correct 939 ms 78536 KB Output is correct
3 Correct 938 ms 78568 KB Output is correct
4 Correct 973 ms 78572 KB Output is correct
5 Correct 925 ms 78572 KB Output is correct
6 Correct 948 ms 78560 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 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
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 78524 KB Output is correct
2 Correct 939 ms 78536 KB Output is correct
3 Correct 938 ms 78568 KB Output is correct
4 Correct 973 ms 78572 KB Output is correct
5 Correct 925 ms 78572 KB Output is correct
6 Correct 948 ms 78560 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 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 1094 ms 78364 KB Output is correct
14 Correct 1002 ms 75112 KB Output is correct
15 Correct 941 ms 74988 KB Output is correct
16 Correct 964 ms 74988 KB Output is correct
17 Correct 1595 ms 76524 KB Output is correct
18 Correct 1600 ms 76392 KB Output is correct
19 Correct 1614 ms 76396 KB Output is correct
20 Correct 1599 ms 76520 KB Output is correct
21 Correct 1585 ms 76616 KB Output is correct
22 Correct 1665 ms 76496 KB Output is correct
23 Correct 1598 ms 76512 KB Output is correct
24 Correct 1577 ms 76452 KB Output is correct
25 Correct 992 ms 78880 KB Output is correct
26 Correct 1008 ms 78744 KB Output is correct
27 Correct 1634 ms 76860 KB Output is correct
28 Correct 1696 ms 76764 KB Output is correct
29 Correct 1697 ms 76764 KB Output is correct
30 Correct 1706 ms 76872 KB Output is correct
31 Correct 1683 ms 76764 KB Output is correct
32 Correct 1016 ms 78348 KB Output is correct
33 Correct 2 ms 376 KB Output is correct