Submission #218073

#	Time	Username	Problem	Language	Result	Execution time	Memory
218073		rama_pang	Examination (JOI19_examination)	C++14	100 / 100	2665 ms	140032 KiB

examination

#include <bits/stdc++.h>
using namespace std;

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

template<typename T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


struct Triple {
  int A, B, C;
  Triple() {}
  Triple(int A, int B, int C) : A(A), B(B), C(C) {}
  bool operator < (const Triple &o) const { return C < o.C; }
};

int N, Q;
vector<pair<Triple, int>> student;
vector<pair<Triple, int>> query;

vector<int> answer;
vector<ordered_set<pair<int, int>>> seg; // merge sort tree with insertions and lower bound operation

void InsertElement(int pos, pair<int, int> elem) {
  for (pos += N; pos > 0; pos /= 2) {
    seg[pos].insert(elem);
  }
}

int OrderOfKey(int l, int r, int key) { // find nummber of elements in [l...r] that is < key
  int res = 0;
  for (l += N, r += N; l < r; l /= 2, r /= 2) {
    if (l & 1) res += seg[l++].order_of_key(make_pair(key, -1));
    if (r & 1) res += seg[--r].order_of_key(make_pair(key, -1));
  }
  return res;
}

int NumberOfElements(int l, int r) {
  int res = 0;
  for (l += N, r += N; l < r; l /= 2, r /= 2) {
    if (l & 1) res += seg[l++].size();
    if (r & 1) res += seg[--r].size();
  }
  return res;
}

void read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> Q;

  for (int i = 0; i < N; i++) {
    int A, B;
    cin >> A >> B;
    student.emplace_back(Triple(A, B, A + B), i);
  }

  for (int i = 0; i < Q; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    query.emplace_back(Triple(A, B, C), i);
    answer.emplace_back(-1);
  }
}

void solve() {
  vector<pair<int, int>> allA; // coordinate compression
  for (int i = 0; i < N; i++) {
    allA.emplace_back(student[i].first.A, student[i].second);
  }
  sort(begin(allA), end(allA));

  // sort by C, inserting elements that fulfill the required C into the merge sort tree
  sort(begin(student), end(student));
  sort(begin(query), end(query));
  reverse(begin(query), end(query));

  seg.resize(2 * N);

  for (auto &q_ : query) {
    Triple q = q_.first;
    int qi = q_.second;

    while (!student.empty() && student.back().first.C >= q.C) {
      int pos = lower_bound(begin(allA), end(allA), make_pair(student.back().first.A, student.back().second)) - begin(allA);
      InsertElement(pos, make_pair(student.back().first.B, student.back().second));
      student.pop_back();
    }

    int l = lower_bound(begin(allA), end(allA), make_pair(q.A, -1)) - begin(allA);
    answer[qi] = NumberOfElements(l, N) - OrderOfKey(l, N, q.B);
  }
}

void write() {
  for (int i = 0; i < Q; i++) {
    cout << answer[i] << "\n";
  }
}

int main() {
  read();
  solve();
  write();
  return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57