oj.uz

Submission #128023

# Submission time Handle Problem Language Result Execution time Memory
128023 2019-07-10T10:34:14 Z RockyB Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 85808 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;

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 <int, ll > > del;
  int last = 1;
  /* rep(i, 1, n) cerr << lst[i] << ' ';
  cerr << nl; */
  for (int i = 1; i <= n && add; i = nxt[i]) {
    int df = (d[i] + last - 1) / last;

    if (!df) ioi
    del.pb({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;
  }
  /* 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 : qr) {
    int L = 0, R = n + 1;
    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 (R <= L) ans[it] += L - R + 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
}

Compilation message

worst_reporter3.cpp: In function 'void solve(ll, std::vector<long long int>&)':
worst_reporter3.cpp:117:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int mid = lo + hi >> 1;
                 ~~~^~~~
worst_reporter3.cpp:123:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int mid = lo + hi >> 1;
                 ~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 85808 KB Output is correct
2 Correct 1905 ms 85656 KB Output is correct
3 Correct 1900 ms 85796 KB Output is correct
4 Correct 1944 ms 85784 KB Output is correct
5 Correct 1844 ms 85624 KB Output is correct
6 Correct 1923 ms 85624 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 636 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 85808 KB Output is correct
2 Correct 1905 ms 85656 KB Output is correct
3 Correct 1900 ms 85796 KB Output is correct
4 Correct 1944 ms 85784 KB Output is correct
5 Correct 1844 ms 85624 KB Output is correct
6 Correct 1923 ms 85624 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 636 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 1708 ms 83760 KB Output is correct
14 Correct 1690 ms 83708 KB Output is correct
15 Correct 1477 ms 83732 KB Output is correct
16 Correct 1578 ms 83740 KB Output is correct
17 Execution timed out 2060 ms 82804 KB Time limit exceeded
18 Halted 0 ms 0 KB -