daily pastebin goal
49%
SHARE
TWEET

arekTOChuj

a guest Aug 12th, 2017 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //DEBUG
  6. #define DEBUG 0
  7.  
  8.  
  9. int KMR[200 * 1000][20];
  10. int n;
  11. int maxKMR;
  12.  
  13. int lastKMRnmbr = 1;
  14.  
  15. pair < pair <int, int>, int> pary[200 * 1000];
  16. int ilePar;
  17.  
  18. int results[100 * 1000];
  19.  
  20. int main()
  21. {
  22.     if(!DEBUG){ios_base::sync_with_stdio(false); cin.tie(0);}
  23.  
  24.     cin >> n;
  25.  
  26.     for(int i = 0; i < n;i++)
  27.     {
  28.         cin >> KMR[i][0];
  29.         KMR[n + i][0] = KMR[i][0];
  30.     }
  31.  
  32.     for(maxKMR = 0; (1 << maxKMR) <= n; maxKMR++); maxKMR--;
  33.  
  34.     for(int lvl = 1; lvl <= maxKMR; lvl++)
  35.     {
  36.         int len = (1 << lvl);
  37.  
  38.         ilePar = 0;
  39.         for(int i = 0; i + len - 1 < 2 * n; i++)
  40.             pary[ilePar++] = {{KMR[i][lvl - 1], KMR[i + len/2][lvl - 1]}, i};
  41.  
  42.         sort(pary, pary + ilePar);
  43.  
  44.         if(DEBUG){for(int p = 0; p < ilePar; p++)cout << "[(" << pary[p].first.first << ", " << pary[p].first.second << "), " << pary[p].second << "] ";cout << "\n\n";}
  45.  
  46.         lastKMRnmbr++;
  47.         for(int p = 0; p  < ilePar; p++)
  48.         {
  49.             if(p != 0 && pary[p].first != pary[p - 1].first)
  50.                 lastKMRnmbr++;
  51.  
  52.             KMR[pary[p].second][lvl] = lastKMRnmbr;
  53.         }
  54.     }
  55.  
  56.     if(DEBUG)
  57.     for(int lvl = 0; lvl <= maxKMR; lvl++)
  58.     {
  59.         for(int i = 0; i < 2 * n; i++)
  60.             cout << KMR[i][lvl] << ' ';
  61.  
  62.         cout << '\n';
  63.     }
  64.  
  65.  
  66.     for(int i = 0; i < n; i++)
  67.         results[i] = i;
  68.  
  69.     sort(results, results + n, [](const int &a, const int &b)->bool
  70.          {
  71.             return (KMR[a][maxKMR] < KMR[b][maxKMR]) || (KMR[a][maxKMR] == KMR[b][maxKMR] && KMR[a + n - (1<<maxKMR)][maxKMR] < KMR[b + n - (1<<maxKMR)][maxKMR]);
  72.          });
  73.  
  74.     if(DEBUG)
  75.     {
  76.         cout << "\n\nRESULTS:\n";
  77.         for(int i = 0; i < n; i++)
  78.             cout << results[i] << '\n';
  79.         cout << "\n\n";
  80.     }
  81.  
  82.     int qNmbr; cin >> qNmbr;
  83.  
  84.     for(int q = 0; q < qNmbr; q++)
  85.     {
  86.         int x, y;
  87.         cin >> x >> y; x--; y--;
  88.  
  89.         cout << KMR[results[y] + x][0] << '\n';
  90.     }
  91.  
  92.  
  93.     return 0;
  94. }
RAW Paste Data
Top