oj.uz

Submission #128022

# Submission time Handle Problem Language Result Execution time Memory
128022 2019-07-10T10:33:22 Z RockyB Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 101496 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)1e6 + 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 1889 ms 85752 KB Output is correct
2 Correct 1880 ms 85732 KB Output is correct
3 Correct 1855 ms 85684 KB Output is correct
4 Correct 1887 ms 85764 KB Output is correct
5 Correct 1898 ms 85724 KB Output is correct
6 Correct 1866 ms 85768 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 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1889 ms 85752 KB Output is correct
2 Correct 1880 ms 85732 KB Output is correct
3 Correct 1855 ms 85684 KB Output is correct
4 Correct 1887 ms 85764 KB Output is correct
5 Correct 1898 ms 85724 KB Output is correct
6 Correct 1866 ms 85768 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 1568 ms 83712 KB Output is correct
14 Correct 1659 ms 100344 KB Output is correct
15 Correct 1504 ms 99192 KB Output is correct
16 Correct 1606 ms 99576 KB Output is correct
17 Execution timed out 2080 ms 101496 KB Time limit exceeded
18 Halted 0 ms 0 KB -