Advertisement
VladIstLove

Untitled

Apr 15th, 2021
563
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. int find_min(std::vector<int>& N, std::vector<int>& M) {
  4.     int left = 0;
  5.     int right = N.size();
  6.     while (right - left > 1) {
  7.         if (N[(left + right) / 2] - M[(left + right) / 2] > 0) {
  8.             right = (left + right) / 2;
  9.         } else {
  10.             left = (left + right) / 2;
  11.         }
  12.     }
  13.     if (left > 0 && (std::max(M[left - 1], N[left - 1]) < std::max(M[left], N[left]))) {
  14.         left = left - 1;
  15.     }
  16.     if (left < N.size() - 1 && (std::max(M[left + 1], N[left + 1]) < std::max(M[left], N[left]))) {
  17.         left = left + 1;
  18.     }
  19.     return left;
  20. }
  21.  
  22. signed main () {
  23.     std::cin.tie(nullptr);
  24.     std::ios_base::sync_with_stdio(false);
  25.     int N, M, D;
  26.     std::cin >> N >> M >> D;
  27.     std::vector<std::vector<int>> N_mas(N);
  28.     for (int i = 0; i < N; ++i) {
  29.         N_mas[i].resize(D);
  30.     }
  31.     std::vector<std::vector<int>> M_mas(M);
  32.     for (int i = 0; i < M; ++i) {
  33.         M_mas[i].resize(D);
  34.     }
  35.     std::map<std::pair<int, int>, int> ans;
  36.     int x;
  37.     for (int i = 0; i < N; ++i) {
  38.         for (int j = 0; j < D; ++j) {
  39.             std::cin >> x;
  40.             N_mas[i][j] = x;
  41.         }
  42.     }
  43.     for (int i = 0; i < M; ++i) {
  44.         for (int j = 0; j < D; ++j) {
  45.             std::cin >> x;
  46.             M_mas[i][j] = x;
  47.         }
  48.     }
  49.     int y;
  50.     int q;
  51.     int day;
  52.     std::cin >> q;
  53.     for (int i = 0; i < q; ++i) {
  54.         std::cin >> x;
  55.         std::cin >> y;
  56.         x -= 1;
  57.         y -= 1;
  58.         if (ans.find({x,y}) != ans.end()) {
  59.             std::cout << ans[{x, y}] + 1 << std::endl;
  60.         } else {
  61.             day = find_min(N_mas[x], M_mas[y]);
  62.             ans[{x, y}] = day;
  63.             std::cout << day + 1 << std::endl;
  64.         }
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement