fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4.  
  5. struct Seg {
  6.     int n;
  7.     vector<int> t;
  8.     Seg(int n) : n(n) { t.assign(4 * n, INF); }
  9.     void upd(int i, int v, int idx, int l, int r) {
  10.         if (l == r) { t[idx] = v; return; }
  11.         int mid = (l + r) / 2;
  12.         if (i <= mid) upd(i, v, 2 * idx, l, mid);
  13.         else         upd(i, v, 2 * idx + 1, mid + 1, r);
  14.         t[idx] = min(t[2 * idx], t[2 * idx + 1]);
  15.     }
  16.     void upd(int i, int v) { upd(i, v, 1, 1, n); }
  17.     int qry(int ql, int qr, int idx, int l, int r) {
  18.         if (qr < l || r < ql) return INF;
  19.         if (ql <= l && r <= qr) return t[idx];
  20.         int mid = (l + r) / 2;
  21.         return min(qry(ql, qr, 2 * idx, l, mid), qry(ql, qr, 2 * idx + 1, mid + 1, r));
  22.     }
  23.     int qry(int ql, int qr) { return qry(ql, qr, 1, 1, n); }
  24. };
  25.  
  26. struct Q { 
  27.     int l, r, id; 
  28. };
  29.  
  30. int main(){
  31.     ios::sync_with_stdio(false);
  32.     cin.tie(nullptr);
  33.  
  34.     int n, m;
  35.     cin >> n >> m;
  36.  
  37.     vector<int> a(n + 1);
  38.     for (int i = 1; i <= n; i++)
  39.         cin >> a[i];
  40.  
  41.     // Tính nxt[i]: chỉ số xuất hiện kế tiếp của a[i]
  42.     vector<int> nxt(n + 1, INF);
  43.     unordered_map<int, int> last;
  44.     for (int i = n; i >= 1; i--){
  45.         if (last.count(a[i])) nxt[i] = last[a[i]];
  46.         last[a[i]] = i;
  47.     }
  48.  
  49.     // Tạo danh sách các sự kiện: (r_th, vị trí i, khoảng cách = nxt[i] - i)
  50.     vector<tuple<int, int, int>> ev;
  51.     for (int i = 1; i <= n; i++){
  52.         if (nxt[i] != INF)
  53.             ev.push_back({nxt[i], i, nxt[i] - i});
  54.     }
  55.     sort(ev.begin(), ev.end(), [](auto &e1, auto &e2){
  56.         return get<0>(e1) < get<0>(e2);
  57.     });
  58.  
  59.     // Đọc và sắp xếp các truy vấn theo r tăng dần
  60.     vector<Q> qs(m);
  61.     for (int i = 0; i < m; i++){
  62.         int l, r;
  63.         cin >> l >> r;
  64.         qs[i] = {l, r, i};
  65.     }
  66.     sort(qs.begin(), qs.end(), [](const Q &q1, const Q &q2){
  67.         return q1.r < q2.r;
  68.     });
  69.  
  70.     Seg seg(n);
  71.     vector<int> ans(m, -1);
  72.     int j = 0;
  73.     for (auto &q : qs){
  74.         while (j < ev.size() && get<0>(ev[j]) <= q.r) {
  75.             int pos = get<1>(ev[j]);
  76.             int d = get<2>(ev[j]);
  77.             seg.upd(pos, d);
  78.             j++;
  79.         }
  80.         int res = seg.qry(q.l, q.r);
  81.         if (res == INF) res = -1;
  82.         ans[q.id] = res;
  83.     }
  84.  
  85.     for (auto x : ans)
  86.         cout << x << "\n";
  87.  
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Jv1tgo
language:
C++14 (clang 8.0)
created:
2 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!