oj.uz

Submission #698017

# Submission time Handle Problem Language Result Execution time Memory
698017 2023-02-11T21:17:11 Z MattTheNub Sails (IOI07_sails) C++17
100 / 100
 194 ms 3720 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T> using v = vector<T>;
using ll = long long;
using dd = long double;
using int2 = pair<int, int>;
using ll2 = pair<ll, ll>;
using dd2 = pair<dd, dd>;

#define f first
#define s second
#define all(x) begin(x), end(x)
#ifdef DEV_MODE
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';
#define dbgp(x)                                                                \
  cerr << "[" << __LINE__ << "] " << #x << " = {" << (x).f << ", " << (x).s    \
       << "}" << '\n';
#else
#define dbg(x)
#define dbgp(x)
#endif

template <class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <class T> istream &operator>>(istream &in, v<T> &v) {
  for (auto &x : v)
    in >> x;
  return in;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
 _______________________________________
( If you don't fail at least 90% of the )
( time, you're not aiming high enough.  )
(                                       )
( - Alan Kay                            )
 ---------------------------------------
        o   ^__^
         o  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||
*/

// MULTITEST TOGGLE
const bool MULTITEST = false;
/******************************************************************************/

template <class T> struct BIT {
  v<T> bit;

  BIT(int n) : bit(n + 1) {}
  void add(int p, T val) {
    for (; p < (int)bit.size(); p += p & (-p))
      bit[p] += val;
  }
  void set(int p, T val) { add(p, val - get(p)); }
  T qry(int p) {
    T sum = 0;
    for (; p > 0; p -= p & (-p))
      sum += bit[p];
    return sum;
  }
  T get(int p) { return qry(p) - qry(p - 1); }
  T sum(int l, int r) { return qry(r) - qry(l - 1); }
};

template <class T> struct RBIT {
  BIT<T> bit1, bit2;

  RBIT(int n) : bit1(n + 1), bit2(n + 1) {}

  void add(int p, T val) {
    bit2.add(1, val);
    bit2.add(p + 1, -val);
    bit1.add(p + 1, p * val);
  }
  void add(int l, int r, T val) {
    add(l - 1, -val);
    add(r, val);
  }

  void set(int p, T val) { add(p, p, val - get(p)); }

  T qry(int p) { return bit2.qry(p) * p + bit1.qry(p); }
  T sum(int l, int r) { return qry(r) - qry(l - 1); }
  T get(int p) { return qry(p) - qry(p - 1); }
};

int search(RBIT<ll> &bit, int x) {
  int lo = 1;
  int hi = bit.bit1.bit.size() - 2;

  while (lo < hi) {
    int mid = (lo + hi) / 2 + 1;
    if (bit.get(mid) >= x) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  if (bit.get(lo) < x)
    lo--;
  return lo;
}

void solve() {
  int n;
  cin >> n;

  v<int2> h(n);
  cin >> h;

  RBIT<ll> num(1e5);
  sort(all(h));
  for (auto x : h) {
    int k = num.get(x.f - x.s + 1);
    int l = search(num, k + 1) + 1, r = search(num, k) + 1;
    // dbg(l);
    num.add(l, min(l + x.s - 1, l + r - x.f + x.s - 2), 1);
    if (r <= x.f)
      num.add(r, x.f, 1);
  }
  ll ans = 0;
  for (int i = 1; i <= 1e5; i++) {
    ans += num.get(i) * (num.get(i) - 1) / 2;
  }
  cout << ans;
}

int main() {
#ifdef DEV_MODE
  freopen("misc-in.txt", "r", stdin);
#else
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int t;
  if (MULTITEST)
    cin >> t;
  else
    t = 1;
  while (t--)
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 1876 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 1876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1876 KB Output is correct
2 Correct 5 ms 1868 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1876 KB Output is correct
2 Correct 6 ms 1876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 8 ms 1920 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1876 KB Output is correct
2 Correct 49 ms 2356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2280 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 2476 KB Output is correct
2 Correct 156 ms 3388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 2516 KB Output is correct
2 Correct 156 ms 2588 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 2672 KB Output is correct
2 Correct 181 ms 3720 KB Output is correct