fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int64_t base = 250007;
  6. const int64_t mod = 1e9 + 2277;
  7.  
  8. int main() {
  9.   ios_base::sync_with_stdio(0);
  10.   cin.tie(0);
  11.   cout.tie(0);
  12. #define task "a"
  13.   if (fopen(task ".inp", "r")) {
  14.     freopen(task ".inp", "r", stdin);
  15.     freopen(task ".out", "w", stdout);
  16.   }
  17.   int n, m;
  18.   cin >> n >> m;
  19.   vector<vector<int>> a(n, vector<int>(m));
  20.   for (auto& i : a) {
  21.     for (auto& j : i) {
  22.       cin >> j;
  23.     }
  24.   }
  25.   if (n > m) {
  26.     vector<vector<int>> b(m, vector<int>(n));
  27.     for (int i = 0; i < n; i++) {
  28.       for (int j = 0; j < m; j++) {
  29.         b[j][i] = a[i][j];
  30.       }
  31.     }
  32.     a = b;
  33.     swap(n, m);
  34.   }
  35.   vector<vector<int>> id = a;
  36.   for (int r = 0; r < n; r++) {
  37.     iota(id[r].begin(), id[r].end(), 0);
  38.     sort(id[r].begin(), id[r].end(), [&](int i, int j) { return a[r][i] > a[r][j]; });
  39.   }
  40.   vector<vector<int>> h(n, vector<int>(m));
  41.   vector<int> rows(n);
  42.   vector<vector<int>> b = a;
  43.   iota(rows.begin(), rows.end(), 0);
  44.   vector<vector<int>> ans = a;
  45.   for (int first_row = 0; first_row < n; first_row++) {
  46.     // move first_row to 1st row
  47.     // maximum lexicographic --> sort decreasing 1st row
  48.     for (int r = 0; r < n; r++) {
  49.       for (int c = 0; c < m; c++) {
  50.         if (!c) {
  51.           h[r][c] = a[r][id[first_row][c]];
  52.         } else {
  53.           h[r][c] = (1ll * h[r][c - 1] * base + a[r][id[first_row][c]]) % mod;
  54.         }
  55.       }
  56.     }
  57.     sort(rows.begin(), rows.end(), [&](const int& i, const int& j) -> bool {
  58.       int l = 0, r = m - 1;
  59.       int d = -1;
  60.       while (l <= r) {
  61.         int mid = (l + r) >> 1;
  62.         if (h[i][mid] != h[j][mid]) {
  63.           d = mid;
  64.           r = mid - 1;
  65.         } else {
  66.           l = mid + 1;
  67.         }
  68.       }
  69.       if (d == -1) return 0;
  70.       return h[i][d] > h[j][d];
  71.     });
  72.     int cmp = 0;
  73.     for (int i = 0; i < n && !cmp; i++) {
  74.       for (int j = 0; j < m && !cmp; j++) {
  75.         int cur = a[rows[i]][id[first_row][j]];
  76.         if (cur == ans[i][j]) {
  77.           continue;
  78.         } else if (cur < ans[i][j]) {
  79.           cmp = -1;
  80.           break;
  81.         } else {
  82.           cmp = 1;
  83.           break;
  84.         }
  85.       }
  86.     }
  87.     if (cmp) {
  88.       for (int i = 0; i < n; i++) {
  89.         for (int j = 0; j < m; j++) {
  90.           ans[i][j] = a[rows[i]][id[first_row][j]];
  91.         }
  92.       }
  93.     }
  94.   }
  95.   int q;
  96.   cin >> q;
  97.   while (q--) {
  98.     int x, y;
  99.     cin >> x >> y;
  100.     cout << ans[--x][--y] << "\n";
  101.   }
  102.   return 0;
  103. }
  104.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
2 3
1 2 3
1 2 3
2
1 1
2 3
stdout
copy 
3
1
https://ideone.com/M0XW3r
language:
C++14 (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!