oj.uz

답안 #954735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954735 2024-03-28T13:04:31 Z evenvalue Examination (JOI19_examination) C++17
100 / 100
 394 ms 43464 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef evenvalue
  #include "debug.h"
#else
  #define debug(...)
#endif

using int64 = long long;
using ld = long double;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

namespace Read {
int Int() {
  int x;
  cin >> x;
  return x;
}
int64 Int64() {
  int64 x;
  cin >> x;
  return x;
}
char Char() {
  char c;
  cin >> c;
  return c;
}
string String() {
  string s;
  cin >> s;
  return s;
}
double Double() {
  return stod(String());
}
ld LongDouble() {
  return stold(String());
}
template<typename T1, typename T2>
pair<T1, T2> Pair() {
  pair<T1, T2> p;
  cin >> p.first >> p.second;
  return p;
}
template<typename T>
vector<T> Vec(const int n) {
  vector<T> v(n);
  for (T &x : v) {
    cin >> x;
  }
  return v;
}
template<typename T>
vector<vector<T>> VecVec(const int n, const int m) {
  vector<vector<T>> v(n);
  for (vector<T> &vec : v) {
    vec = Vec<T>(m);
  }
  return v;
}
}//namespace Read

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kMaxN = 2e5 + 10;

class MergeSortTree {
  const int n;
  vector<vector<int>> t;

  void build(const int x, const int l, const int r, const vector<int> &a) {
    if (l == r) {
      t[x] = {a[l]};
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    build(x + 1, l, mid, a);
    build(y, mid + 1, r, a);
    merge(t[x + 1].begin(), t[x + 1].end(),
          t[y].begin(), t[y].end(),
          back_inserter(t[x]));
  }

  int query(const int x, const int l, const int r, const int ql, const int qr, const int q) {
    if (ql <= l and r <= qr) {
      const auto it = lower_bound(t[x].begin(), t[x].end(), q);
      return distance(it, t[x].end());
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (qr <= mid) {
      return query(x + 1, l, mid, ql, qr, q);
    } else if (mid < ql) {
      return query(y, mid + 1, r, ql, qr, q);
    } else {
      return query(x + 1, l, mid, ql, qr, q) + query(y, mid + 1, r, ql, qr, q);
    }
  }

public:
  MergeSortTree(const vector<int> &a) : n(a.size()), t(2 * n - 1) {
    build(0, 0, n - 1, a);
  }

  int query(const int ql, const int qr, const int q) {
    if (ql > qr) return 0;
    return query(0, 0, n - 1, ql, qr, q);
  }
};

struct Student {
  int math;
  int info;

  bool operator<(const Student &other) const {
    return math < other.math;
  }
};

inline void solution() {
  const int n = Read::Int();
  const int m = Read::Int();

  vector<Student> students(n);
  for (auto &[a, b] : students) {
    a = Read::Int();
    b = Read::Int();
  }

  sort(students.begin(), students.end());

  vector<int> sum(n);
  for (int i = 0; i < n; i++) {
    sum[i] = students[i].math + students[i].info;
  }

  vector<int> informatics(n);
  for (int i = 0; i < n; i++) {
    informatics[i] = students[i].info;
  }

  auto get_range = [&](const int l, const int r) -> pair<int, int> {
    int lo = 0, hi = n;
    while (lo < hi) {
      const int mid = (lo + hi) / 2;
      if (students[mid].math >= l) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    const int left = lo;
    lo = -1, hi = n - 1;
    while (lo < hi) {
      const int mid = (lo + hi + 1) / 2;
      if (students[mid].math >= r) {
        hi = mid - 1;
      } else {
        lo = mid;
      }
    }
    const int right = lo;
    return {left, right};
  };

  MergeSortTree total(sum);
  MergeSortTree info(informatics);

  for (int qry = 0; qry < m; qry++) {
    const int a = Read::Int();
    const int b = Read::Int();
    const int c = Read::Int();
    const auto [l1, r1] = get_range(a, c - b);
    const auto [l2, r2] = get_range(max(a, c - b), kInf);

    const int part1 =  total.query(l1, r1, c);
    const int part2 = info.query(l2, r2, b);

    cout << part1 + part2 << '\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  //freopen(".in", "r", stdin);
  //freopen(".out", "w", stdout);

  cout << fixed << setprecision(10);

  int testcases = 1;
  //cin >> testcases;
  while (testcases--) {
    solution();
  }
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 5 ms 1616 KB Output is correct
8 Correct 5 ms 1784 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 4 ms 1372 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1372 KB Output is correct
15 Correct 5 ms 1372 KB Output is correct
16 Correct 3 ms 1372 KB Output is correct
17 Correct 5 ms 1372 KB Output is correct
18 Correct 3 ms 1628 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 40772 KB Output is correct
2 Correct 220 ms 40652 KB Output is correct
3 Correct 225 ms 41124 KB Output is correct
4 Correct 183 ms 40132 KB Output is correct
5 Correct 153 ms 40136 KB Output is correct
6 Correct 114 ms 39260 KB Output is correct
7 Correct 202 ms 40648 KB Output is correct
8 Correct 189 ms 40828 KB Output is correct
9 Correct 183 ms 40728 KB Output is correct
10 Correct 110 ms 40132 KB Output is correct
11 Correct 150 ms 39880 KB Output is correct
12 Correct 84 ms 38856 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 40772 KB Output is correct
2 Correct 220 ms 40652 KB Output is correct
3 Correct 225 ms 41124 KB Output is correct
4 Correct 183 ms 40132 KB Output is correct
5 Correct 153 ms 40136 KB Output is correct
6 Correct 114 ms 39260 KB Output is correct
7 Correct 202 ms 40648 KB Output is correct
8 Correct 189 ms 40828 KB Output is correct
9 Correct 183 ms 40728 KB Output is correct
10 Correct 110 ms 40132 KB Output is correct
11 Correct 150 ms 39880 KB Output is correct
12 Correct 84 ms 38856 KB Output is correct
13 Correct 286 ms 41432 KB Output is correct
14 Correct 261 ms 41156 KB Output is correct
15 Correct 223 ms 40924 KB Output is correct
16 Correct 250 ms 40396 KB Output is correct
17 Correct 156 ms 40376 KB Output is correct
18 Correct 120 ms 39188 KB Output is correct
19 Correct 274 ms 41152 KB Output is correct
20 Correct 279 ms 41124 KB Output is correct
21 Correct 282 ms 41164 KB Output is correct
22 Correct 108 ms 39880 KB Output is correct
23 Correct 161 ms 39880 KB Output is correct
24 Correct 83 ms 38860 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 5 ms 1616 KB Output is correct
8 Correct 5 ms 1784 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 4 ms 1372 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1372 KB Output is correct
15 Correct 5 ms 1372 KB Output is correct
16 Correct 3 ms 1372 KB Output is correct
17 Correct 5 ms 1372 KB Output is correct
18 Correct 3 ms 1628 KB Output is correct
19 Correct 216 ms 40772 KB Output is correct
20 Correct 220 ms 40652 KB Output is correct
21 Correct 225 ms 41124 KB Output is correct
22 Correct 183 ms 40132 KB Output is correct
23 Correct 153 ms 40136 KB Output is correct
24 Correct 114 ms 39260 KB Output is correct
25 Correct 202 ms 40648 KB Output is correct
26 Correct 189 ms 40828 KB Output is correct
27 Correct 183 ms 40728 KB Output is correct
28 Correct 110 ms 40132 KB Output is correct
29 Correct 150 ms 39880 KB Output is correct
30 Correct 84 ms 38856 KB Output is correct
31 Correct 286 ms 41432 KB Output is correct
32 Correct 261 ms 41156 KB Output is correct
33 Correct 223 ms 40924 KB Output is correct
34 Correct 250 ms 40396 KB Output is correct
35 Correct 156 ms 40376 KB Output is correct
36 Correct 120 ms 39188 KB Output is correct
37 Correct 274 ms 41152 KB Output is correct
38 Correct 279 ms 41124 KB Output is correct
39 Correct 282 ms 41164 KB Output is correct
40 Correct 108 ms 39880 KB Output is correct
41 Correct 161 ms 39880 KB Output is correct
42 Correct 83 ms 38860 KB Output is correct
43 Correct 286 ms 43152 KB Output is correct
44 Correct 294 ms 43464 KB Output is correct
45 Correct 264 ms 43208 KB Output is correct
46 Correct 270 ms 41668 KB Output is correct
47 Correct 169 ms 41676 KB Output is correct
48 Correct 120 ms 39112 KB Output is correct
49 Correct 317 ms 43048 KB Output is correct
50 Correct 287 ms 43072 KB Output is correct
51 Correct 394 ms 43232 KB Output is correct
52 Correct 117 ms 41416 KB Output is correct
53 Correct 151 ms 40580 KB Output is correct