Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- int find_min(std::vector<int>& N, std::vector<int>& M) {
- int left = 0;
- int right = N.size();
- while (right - left > 1) {
- if (N[(left + right) / 2] - M[(left + right) / 2] > 0) {
- right = (left + right) / 2;
- } else {
- left = (left + right) / 2;
- }
- }
- if (left > 0 && (std::max(M[left - 1], N[left - 1]) < std::max(M[left], N[left]))) {
- left = left - 1;
- }
- if (left < N.size() - 1 && (std::max(M[left + 1], N[left + 1]) < std::max(M[left], N[left]))) {
- left = left + 1;
- }
- return left;
- }
- signed main () {
- std::cin.tie(nullptr);
- std::ios_base::sync_with_stdio(false);
- int N, M, D;
- std::cin >> N >> M >> D;
- std::vector<std::vector<int>> N_mas(N);
- for (int i = 0; i < N; ++i) {
- N_mas[i].resize(D);
- }
- std::vector<std::vector<int>> M_mas(M);
- for (int i = 0; i < M; ++i) {
- M_mas[i].resize(D);
- }
- std::map<std::pair<int, int>, int> ans;
- int x;
- for (int i = 0; i < N; ++i) {
- for (int j = 0; j < D; ++j) {
- std::cin >> x;
- N_mas[i][j] = x;
- }
- }
- for (int i = 0; i < M; ++i) {
- for (int j = 0; j < D; ++j) {
- std::cin >> x;
- M_mas[i][j] = x;
- }
- }
- int y;
- int q;
- int day;
- std::cin >> q;
- for (int i = 0; i < q; ++i) {
- std::cin >> x;
- std::cin >> y;
- x -= 1;
- y -= 1;
- if (ans.find({x,y}) != ans.end()) {
- std::cout << ans[{x, y}] + 1 << std::endl;
- } else {
- day = find_min(N_mas[x], M_mas[y]);
- ans[{x, y}] = day;
- std::cout << day + 1 << std::endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement