fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pub push_back
  3. #define log2(x) (x > 0 ? 63 - __builtin_clzll(x) : -1)
  4. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  5. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  6. #define pii pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define all(x) begin(x), end(x)
  10. #define int long long
  11. #define index iii
  12. using namespace std;
  13.  
  14. const int N = 2e5 + 5;
  15. const int M = 350;
  16. const int LOG = 19;
  17. const int inf = 3e18;
  18.  
  19. struct thi {int fi, se, th; };
  20.  
  21. int n, q, a[N], out[N];
  22. int block = 0;
  23. thi query[N];
  24. int mp[N];
  25.  
  26. int last[N], first[N];
  27. deque <int> indx[N];
  28. multiset <int> ans;
  29.  
  30. bool cmp(thi &a, thi &b) {
  31.     if (a.fi / block == b.fi / block) return a.se < b.se;
  32.     return a.fi < b.fi;
  33. }
  34. void input() {
  35.     cin >> n;
  36.     block = (int)sqrt(n);
  37.     FOR(i, 1, n, 1) {
  38.         cin >> a[i];
  39.     }
  40.     cin >> q;
  41.     FOR(i, 1, q, 1) {
  42.         cin >> query[i].fi >> query[i].se;
  43.         query[i].th = i;
  44.     }
  45.     sort(query + 1, query + q + 1, cmp);
  46. }
  47.  
  48. void del(int o, int &x, int &inx) {
  49.     int old_dis = indx[x].back() - indx[x].front();
  50.     ans.erase(ans.find(old_dis));
  51.  
  52.     if (o == 1) indx[x].pop_front();
  53.     if (o == 2) indx[x].pop_back();
  54.  
  55.     if (!indx[x].empty()) {
  56.         int new_dis = indx[x].back() - indx[x].front();
  57.         ans.insert(new_dis);
  58.     }
  59. }
  60. void add(int o, int &x, int &inx) {
  61.     if (!indx[x].empty()) {
  62.         int old_dis = indx[x].back() - indx[x].front();
  63.         ans.erase(ans.find(old_dis));
  64.     }
  65.  
  66.     if (o == 1) indx[x].push_front(inx);
  67.     if (o == 2) indx[x].push_back(inx);
  68.  
  69.     int new_dis = indx[x].back() - indx[x].front();
  70.     ans.insert(new_dis);
  71. }
  72. void solve() {
  73.     input();
  74.  
  75.     int L = 1, R = 0;
  76.  
  77.     FOR(i, 1, q, 1) {
  78.         int l = query[i].fi;
  79.         int r = query[i].se;
  80.         int id = query[i].th;
  81.  
  82.         while(L > l) add(1, a[--L], i);
  83.         while(R < r) add(2, a[++R], i);
  84.         while(L < l) del(1, a[L++], i);
  85.         while(R > r) del(2, a[R--], i);
  86.  
  87.         if (ans.empty()) {
  88.             out[id] = 0;
  89.         } else {
  90.             out[id] = *ans.rbegin();
  91.         }
  92.     }
  93.     FOR(i, 1, q, 1) {
  94.         cout << out[i] << '\n';
  95.     }
  96. }
  97. signed main() {
  98.     #define name "baitap"
  99.     if (ifstream(name".inp")) {
  100.         freopen(name".inp", "r", stdin);
  101.         freopen(name".out", "w", stdout);
  102.     }
  103.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  104.     solve();
  105. }
  106.  
Success #stdin #stdout 0.12s 141032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AzoelR
language:
C++ (gcc 8.3)
created:
1 day 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!