oj.uz

Submission #954738

# Submission time Handle Problem Language Result Execution time Memory
954738 2024-03-28T13:06:03 Z evenvalue Examination (JOI19_examination) C++17
100 / 100
 356 ms 41164 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);
    cout << total.query(l1, r1, c) + info.query(l2, r2, b) << '\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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 6 ms 1628 KB Output is correct
8 Correct 5 ms 1628 KB Output is correct
9 Correct 5 ms 1624 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 4 ms 1596 KB Output is correct
12 Correct 4 ms 1500 KB Output is correct
13 Correct 5 ms 1624 KB Output is correct
14 Correct 5 ms 1368 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 1484 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 39900 KB Output is correct
2 Correct 213 ms 39800 KB Output is correct
3 Correct 217 ms 39884 KB Output is correct
4 Correct 191 ms 39292 KB Output is correct
5 Correct 155 ms 39372 KB Output is correct
6 Correct 118 ms 39080 KB Output is correct
7 Correct 206 ms 39740 KB Output is correct
8 Correct 196 ms 39864 KB Output is correct
9 Correct 182 ms 39628 KB Output is correct
10 Correct 110 ms 39112 KB Output is correct
11 Correct 157 ms 39112 KB Output is correct
12 Correct 93 ms 38752 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 39900 KB Output is correct
2 Correct 213 ms 39800 KB Output is correct
3 Correct 217 ms 39884 KB Output is correct
4 Correct 191 ms 39292 KB Output is correct
5 Correct 155 ms 39372 KB Output is correct
6 Correct 118 ms 39080 KB Output is correct
7 Correct 206 ms 39740 KB Output is correct
8 Correct 196 ms 39864 KB Output is correct
9 Correct 182 ms 39628 KB Output is correct
10 Correct 110 ms 39112 KB Output is correct
11 Correct 157 ms 39112 KB Output is correct
12 Correct 93 ms 38752 KB Output is correct
13 Correct 280 ms 40140 KB Output is correct
14 Correct 265 ms 40136 KB Output is correct
15 Correct 214 ms 39880 KB Output is correct
16 Correct 272 ms 39944 KB Output is correct
17 Correct 161 ms 39624 KB Output is correct
18 Correct 122 ms 39116 KB Output is correct
19 Correct 289 ms 39928 KB Output is correct
20 Correct 290 ms 40140 KB Output is correct
21 Correct 291 ms 40316 KB Output is correct
22 Correct 111 ms 39024 KB Output is correct
23 Correct 154 ms 39112 KB Output is correct
24 Correct 86 ms 38928 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 6 ms 1628 KB Output is correct
8 Correct 5 ms 1628 KB Output is correct
9 Correct 5 ms 1624 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 4 ms 1596 KB Output is correct
12 Correct 4 ms 1500 KB Output is correct
13 Correct 5 ms 1624 KB Output is correct
14 Correct 5 ms 1368 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 1484 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 217 ms 39900 KB Output is correct
20 Correct 213 ms 39800 KB Output is correct
21 Correct 217 ms 39884 KB Output is correct
22 Correct 191 ms 39292 KB Output is correct
23 Correct 155 ms 39372 KB Output is correct
24 Correct 118 ms 39080 KB Output is correct
25 Correct 206 ms 39740 KB Output is correct
26 Correct 196 ms 39864 KB Output is correct
27 Correct 182 ms 39628 KB Output is correct
28 Correct 110 ms 39112 KB Output is correct
29 Correct 157 ms 39112 KB Output is correct
30 Correct 93 ms 38752 KB Output is correct
31 Correct 280 ms 40140 KB Output is correct
32 Correct 265 ms 40136 KB Output is correct
33 Correct 214 ms 39880 KB Output is correct
34 Correct 272 ms 39944 KB Output is correct
35 Correct 161 ms 39624 KB Output is correct
36 Correct 122 ms 39116 KB Output is correct
37 Correct 289 ms 39928 KB Output is correct
38 Correct 290 ms 40140 KB Output is correct
39 Correct 291 ms 40316 KB Output is correct
40 Correct 111 ms 39024 KB Output is correct
41 Correct 154 ms 39112 KB Output is correct
42 Correct 86 ms 38928 KB Output is correct
43 Correct 294 ms 41000 KB Output is correct
44 Correct 286 ms 41164 KB Output is correct
45 Correct 270 ms 40908 KB Output is correct
46 Correct 263 ms 40140 KB Output is correct
47 Correct 171 ms 40316 KB Output is correct
48 Correct 120 ms 38864 KB Output is correct
49 Correct 310 ms 40732 KB Output is correct
50 Correct 271 ms 40716 KB Output is correct
51 Correct 356 ms 41000 KB Output is correct
52 Correct 124 ms 39888 KB Output is correct
53 Correct 155 ms 39672 KB Output is correct