fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7.  
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. using namespace __gnu_pbds;
  11.  
  12. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  13. typedef pair<int, int>pr;
  14. #define all(i)     i.begin() , i.end()
  15. #define ft     first
  16. #define sn     second
  17. #define pb push_back
  18.  
  19. #define dbg cout<<"rony\n"
  20. #define en "\n"
  21.  
  22. #define MAXN 100010
  23. #define inf 1e6+5
  24. const ll mod = 1e9 + 7;
  25.  
  26. int n, c, q;
  27. int a[MAXN];
  28.  
  29. struct SegmentTree
  30. {
  31.     struct node
  32.     {
  33.         int preval, sufval, precnt, sufcnt, an, suru, ses;
  34.         void init(int l, int r)
  35.         {
  36.             suru = l, ses = r;
  37.             if (l == r) {
  38.                 preval = sufval = a[l];
  39.                 an = precnt = sufcnt = 1;
  40.             }
  41.         }
  42.     } g[4 * MAXN], ans;
  43.  
  44.     node fill_cn(int l, int r, node B, node C)
  45.     {
  46.         node A;
  47.  
  48.         if (B.preval == -1) {
  49.             return C;
  50.         }
  51.         if (C.preval == -1) return B;
  52.         if (B.preval == C.sufval) {
  53.             A.preval = B.preval; A.sufval = B.sufval;
  54.             A.precnt = B.precnt + C.precnt;
  55.             A.sufcnt = B.sufcnt + C.sufcnt;
  56.             A.an = A.precnt;
  57.         }
  58.         else if (B.preval == B.sufval && B.sufval == C.preval) {
  59.             A.preval = B.preval; A.sufval = C.sufval;
  60.             A.precnt = B.precnt + C.precnt;
  61.             A.sufcnt = C.sufcnt;
  62.             A.an = max({B.an, C.an, A.precnt});
  63.         }
  64.         else if (B.sufval == C.preval && C.sufval == C.preval) {
  65.             A.preval = B.preval; A.sufval = B.sufval;
  66.             A.precnt = B.precnt; A.sufcnt = B.sufcnt + C.precnt;
  67.             A.an = max({B.an, C.an, A.sufcnt});
  68.         }
  69.         else if (B.sufval == C.preval) {
  70.             A.preval = B.preval; A.sufval = C.sufval;
  71.             A.precnt = B.precnt; A.sufcnt = C.sufcnt;
  72.             A.an = max({B.an, C.an, B.sufcnt + C.precnt });
  73.         }
  74.         else {
  75.             A.preval = B.preval; A.sufval = C.sufval;
  76.             A.precnt = B.precnt; A.sufcnt = C.sufcnt;
  77.  
  78.             A.an = max({B.an, C.an, B.sufcnt, C.precnt});
  79.         }
  80.  
  81.         return A;
  82.     }
  83.  
  84.     void build(int cn, int l, int r)
  85.     {
  86.         g[cn].init(l, r);
  87.         if (l == r) return ;
  88.         int md = l + (r - l) / 2;
  89.         build(cn * 2, l, md);
  90.         build(cn * 2 + 1, md + 1, r);
  91.  
  92.         g[cn] = fill_cn( l, r, g[cn * 2], g[cn * 2 + 1]);
  93.         g[cn].suru = l; g[cn].ses = r;
  94.     }
  95.  
  96.     node makend()
  97.     {
  98.         node A;
  99.         A.preval = A.sufval = A.precnt = A.sufcnt = A.an = -1;
  100.         return A;
  101.     }
  102.  
  103.     node query(int cn, int l, int r)
  104.     {
  105.         int x = g[cn].suru;
  106.         int y = g[cn].ses;
  107.         if (y < l || x > r ) {
  108.  
  109.             return makend();
  110.         }
  111.         if (l <= x && y <= r) {
  112.  
  113.             return g[cn];
  114.         }
  115.         node _1 = query( cn * 2, l, r);
  116.         node _2 = query(cn * 2 + 1, l, r);
  117.         return fill_cn(x, y, _1, _2);
  118.     }
  119.  
  120. } stre;
  121.  
  122. void solve()
  123. {
  124.     cin >> n >> c >> q;
  125.  
  126.     for (int i = 1; i <= n; i++) {
  127.         cin >> a[i];
  128.     }
  129.  
  130.     stre.build(1, 1, n);
  131.     // dbg; dbg;
  132.     while (q--)
  133.     {
  134.         int x, y;
  135.         cin >> x >> y;
  136.         stre.ans = stre.query(1, x, y);
  137.         cout << stre.ans.an << en;
  138.     }
  139.     // stre.ans = stre.query(1, 7, 7);
  140.     // cout << stre.ans.an << en;
  141.  
  142. }
  143. int main()
  144. {
  145.     IOS;
  146.     ll t;
  147.     t = 1;
  148.     cin >> t;
  149.  
  150.     ll c = 0;
  151.     while ( t-- )
  152.     {
  153.         cout << "Case " << ++c << ":\n";
  154.         solve();
  155.     }
  156.     return 0;
  157. }
Runtime error #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FJY2OE
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!