fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2.  
  3. #include<bits/stdc++.h>
  4. //#include <ext/pb_ds/assoc_container.hpp>
  5. //#include <ext/pb_ds/trie_policy.hpp>
  6. //#include <ext/rope>
  7.  
  8. //#pragma GCC optimize("Ofast")
  9. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  10. //#pragma GCC target("avx,avx2,fma")
  11.  
  12. //using namespace std;
  13. //using namespace __gnu_pbds;
  14. //using namespace __gnu_cxx;
  15.  
  16. #define fi first
  17. #define se second
  18. #define TASK "test"
  19. #define pb push_back
  20. #define EL cout << endl
  21. #define Ti20_ntson int main()
  22. #define in(x) cout << x << endl
  23. #define all(x) (x).begin(),(x).end()
  24. #define getbit(x, i) (((x) >> (i)) & 1)
  25. #define cntbit(x) __builtin_popcount(x)
  26. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  27. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  28. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  29.  
  30. using namespace std;
  31.  
  32. typedef long long ll;
  33. typedef vector<int> vi;
  34. typedef pair<int,int> vii;
  35. typedef unsigned long long ull;
  36. typedef vector<vector<int>> vvi;
  37.  
  38. const int N = 2e5 + 5;
  39. const int oo = INT_MAX;
  40. const int mod = 1e9 + 7;
  41. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  42. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  43. const int Bl = 333;
  44.  
  45. struct Query {
  46.     int l, r, id;
  47.  
  48.     bool operator < (const Query &T) const {
  49.         if (l / Bl != T.l / Bl)
  50.             return l / Bl < T.l / Bl;
  51.         return r < T.r;
  52.     }
  53.  
  54. }a[N];
  55.  
  56. int n, m, Val[N], c[N], mn[N], mx[N], Ans[N], Ans1, Ans2, mnBl[N], mxBl[N];
  57.  
  58. inline void Read_Input() {
  59.     cin >> n >> m;
  60.     FOR(i, 1, n)
  61.         cin >> Val[i];
  62.     FOR(i, 1, m)
  63.         cin >> a[i].l >> a[i].r, a[i].id = i, a[i].l--;
  64.     sort(a + 1, a + m + 1);
  65. }
  66.  
  67. unordered_map<int, int> mp[N];
  68.  
  69. void Build() {
  70.     c[0] = 1;
  71.     int cnt = 1;
  72.     FOR(i, 1, n) {
  73.         int res = c[i - 1];
  74.         auto it = mp[res].find(-Val[i]);
  75.         if (it != mp[res].end())
  76.             c[i] = c[(*it).se - 1];
  77.         else c[i] = ++cnt;
  78.         mp[c[i]][Val[i]] = i;
  79. //        cout << c[i] << " ";
  80.     }
  81. //    cout << '\n';
  82. }
  83.  
  84. void Add(int id) {
  85.     if (mn[c[id]] == -1) mn[c[id]] = id; mn[c[id]] = min(mn[c[id]], id);
  86.     if (mx[c[id]] == -1) mx[c[id]] = id; mx[c[id]] = max(mx[c[id]], id);
  87.     Ans1 = max(Ans1, mx[c[id]] - mn[c[id]]);
  88. }
  89.  
  90. void AddBl(int id) {
  91.     if (mnBl[c[id]] == -1) mnBl[c[id]] = id; mnBl[c[id]] = min(mnBl[c[id]], id);
  92.     if (mxBl[c[id]] == -1) mxBl[c[id]] = id; mxBl[c[id]] = max(mxBl[c[id]], id);
  93.     Ans2 = max(Ans2, mxBl[c[id]] - mnBl[c[id]]);
  94.     Ans2 = max(Ans2, mx[c[id]] - mnBl[c[id]]);
  95. }
  96.  
  97. inline void Solve() {
  98.     Build();
  99.     int Le, Ri;
  100.     int ct;
  101.     FOR(i, 1, m) {
  102.         if ((i == 1) || (a[i].l / Bl != a[i - 1].l / Bl)) {
  103.             FOR(j, 1, n + 1)
  104.                 mn[j] = -1, mx[j] = -1;
  105.             Le = a[i].l / Bl * Bl;
  106.             Ri = min(n, Le + Bl - 1);
  107.             Ans1 = 0;
  108.             FOR(j, Ri + 1, a[i].r)
  109.                 Add(j);
  110.             ct = max(a[i].r, Ri);
  111.         }
  112.         Ans2 = 0;
  113.         FOR(j, Le, Ri)
  114.             mnBl[c[j]] = -1, mxBl[c[j]] = -1;
  115.         while (ct < a[i].r)
  116.             Add(++ct);
  117.         FOR(j, a[i].l, min(Ri, a[i].r))
  118.             AddBl(j);
  119.         Ans[a[i].id] = max(Ans1, Ans2);
  120.     }
  121.     FOR(i, 1, m)
  122.         cout << Ans[i] << '\n';
  123.  
  124. }
  125.  
  126. Ti20_ntson {
  127. //    freopen(TASK".INP","r",stdin);
  128. //    freopen(TASK".OUT","w",stdout);
  129.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  130.     int T = 1;
  131.     while (T -- ) {
  132.         Read_Input();
  133.         Solve();
  134.     }
  135. }
  136.  
Success #stdin #stdout 0.01s 17680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uFAnPf
language:
C++14 (gcc 8.3)
created:
2 days 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!