fork download
copy 
  1. /*
  2. * Author: Geeza
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define ld long double
  8. #define ll long long
  9. #define pb push_back
  10. #define fin(a, n) for(int i = a; i < n; i++)
  11. #define fjn(a, n) for(int j = a; j < n; j++)
  12. #define all(a) a.begin(),a.end()
  13. #define allr(a) a.rbegin(),a.rend()
  14. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  15.  
  16. using namespace std;
  17.  
  18. const double PI = acos(-1);
  19. const int N = 1e7+10;
  20. const ll oo = 0x3f3f3f3f3f3f3f3f;
  21. const int mod = 1000000007, inf = 1e6;
  22.  
  23. string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
  24. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  25. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  26. char dc[] = {'D', 'L', 'R', 'U'};
  27.  
  28. struct node {
  29.     ll leftVal, rightVal, leftFreq, rightFreq, bst, len;
  30.     node() {leftVal = rightVal = 0, leftFreq = rightFreq = bst = len = 0;}
  31.     node(ll x) {leftVal = rightVal = x, leftFreq = rightFreq = bst = len = 1;}
  32. };
  33.  
  34. struct segTree {
  35.     ll treeSize;
  36.     vector<node> tree;
  37.  
  38.     segTree(ll n) {
  39.         treeSize = 1;
  40.         while (treeSize < n) treeSize <<= 1;
  41.         tree.resize(2 * treeSize, node());
  42.     }
  43.  
  44.     node merge(node l, node r) {
  45.         if (l.len == 0) return r;
  46.         if (r.len == 0) return l;
  47.  
  48.         node parent = node();
  49.         parent.len = l.len + r.len;
  50.         parent.leftVal = l.leftVal;
  51.         parent.rightVal = r.rightVal;
  52.         parent.leftFreq = l.leftFreq;
  53.  
  54.         if (l.leftFreq == l.len && l.rightVal == r.leftVal) parent.leftFreq += r.leftFreq;
  55.         parent.rightFreq = r.rightFreq;
  56.         if (r.rightFreq == r.len && l.rightVal == r.leftVal) parent.rightFreq += l.rightFreq;
  57.         parent.bst = max(l.bst, r.bst);
  58.         if (l.rightVal == r.leftVal) parent.bst = max(parent.bst, l.rightFreq + r.leftFreq);
  59.         return parent;
  60.     }
  61.  
  62.     void build(vector<ll> &v, ll i, ll l, ll r) {
  63.         if (r-l == 1) {
  64.             if (l < v.size()) tree[i] = node(v[l]);
  65.             return;
  66.         }
  67.  
  68.         ll mid = l+(r-l)/2;
  69.         build(v, 2*i+1, l, mid);
  70.         build(v, 2*i+2, mid, r);
  71.         tree[i] = merge(tree[2*i+1], tree[2*i+2]);
  72.     }
  73.  
  74.     void build(vector<ll> &v) {
  75.         build(v, 0, 0, treeSize);
  76.     }
  77.  
  78.     node query(ll l, ll r, ll i, ll lx, ll rx) {
  79.         if (lx >= r || rx <= l) return node();
  80.         if (lx >= l && rx <= r) return tree[i];
  81.  
  82.         ll mid = (lx + rx) / 2;
  83.  
  84.         node left = query(l, r, 2*i+1, lx, mid);
  85.         node right = query(l, r, 2*i+2, mid, rx);
  86.         return merge(left, right);
  87.     }
  88.  
  89.     ll query(ll l, ll r) {
  90.         return query(l, r, 0, 0, treeSize).bst;
  91.     }
  92. };
  93. ll n, q;
  94. void solve() {
  95.     vector<ll> v(n);
  96.     fin(0, n) cin >> v[i];
  97.     segTree st(n);
  98.     st.build(v);
  99.  
  100.     while (q--) {
  101.         ll l, r; cin >> l >> r; l--;
  102.         cout << st.query(l, r) << "\n";
  103.     }
  104. }
  105.  
  106. int main() {
  107. #ifndef ONLINE_JUDGE
  108.     freopen("input.txt","r",stdin);
  109.     freopen("output.txt","w",stdout);
  110. #endif
  111.     int tt = 1; //cin >> tt;
  112.     while(cin >> n){
  113.         if (n == 0) break;
  114.         cin >> q;
  115.         solve();
  116.     }
  117.     return 0;
  118. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XZnMPb
language:
C++ (gcc 8.3)
created:
7 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!