fork download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8. #include <iostream>
  9. #include <sstream>
  10. #include <cstdio>
  11. #include <cmath>
  12. #include <ctime>
  13. #include <cstring>
  14. #include <cctype>
  15. #include <cassert>
  16. #include <limits>
  17. #include <functional>
  18. #include <bitset>
  19. #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
  20. #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
  21. #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
  22. #if defined(_MSC_VER) || __cplusplus > 199711L
  23. #define aut(r,v) auto r = (v)
  24. #else
  25. #define aut(r,v) typeof(v) r = (v)
  26. #endif
  27. #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
  28. #define all(o) (o).begin(), (o).end()
  29. #define pb(x) push_back(x)
  30. #define mp(x,y) make_pair((x),(y))
  31. #define mset(m,v) memset(m,v,sizeof(m))
  32. #define INF 0x3f3f3f3f
  33. #define INFL 0x3f3f3f3f3f3f3f3fLL
  34. #include<bits/stdc++.h>
  35. #define  lld long long int
  36. #define Max 1000000+7
  37. # define it int
  38. using namespace std;
  39. typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
  40. typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
  41. typedef vector<string> vs; typedef long double ld;
  42. template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
  43. template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
  44. it rupc[Max];
  45. lld rupc7[Max];
  46. it n; it q,i,j,k,m;
  47. struct ass{lld y;it x;};ass bazinga[Max];
  48. it forest[3000007];
  49. bool check(ass hole ,ass boobs);
  50. void make(it xxx,it l,it r);
  51. it supckdick(it xxx,it l,it r,it nip,it x);
  52. it supckboobs(it xxx,it l,it r,it nip,it x);
  53. it main()
  54. {   int kl=100000;
  55.     while (kl--){
  56.     	kl-=2;
  57.     }
  58. 	   it l,r,up;
  59.     char c,d;
  60.      cin>>n; // sd(n);
  61.     cin>>q;//sd(q);
  62.     for(i=0;i<n;i++)
  63.        cin>>rupc[i];// sd(rupc[i]);
  64.     make(1,0,n-1);
  65.     for(i=0;i<n;i++)
  66.     { int tt=10;  
  67. 	 while (tt--){tt--;
  68. 	 }
  69.         r=supckboobs(1,0,n-1,rupc[i],i);
  70.         l=supckdick(1,0,n-1,rupc[i],i);
  71.         //printf("%d %d\n",l,r);
  72.         rupc7[i]=(1ll*(r-i+1)*(i-l+1));}
  73.         for(i=0;i<n;i++)
  74.         {
  75.             bazinga[i].x=rupc[i];
  76.             bazinga[i].y=rupc7[i];
  77.         }
  78.         sort(bazinga,bazinga+n,check);
  79.         j=0;k=bazinga[0].y;
  80.         for(i=1;i<n;i++)
  81.         {
  82.             if(bazinga[i].x==bazinga[i-1].x)
  83.             {
  84.                 k+=bazinga[i].y;
  85.             }
  86.             else
  87.             {
  88.                 rupc[j]=bazinga[i-1].x;
  89.                 rupc7[j]=k;
  90.                 k=bazinga[i].y;
  91.                 j++;
  92.             }
  93.         }
  94.         rupc[j]=bazinga[i-1].x;
  95.         rupc7[j]=k;
  96.         for(i=1;i<=j;i++)
  97.             rupc7[i]+=rupc7[i-1];
  98. //        for(i=0;i<=j;i++)
  99. //           printf("%lld \n",rupc7[i]);
  100. //        for(i=0;i<=j;i++)
  101. //        {
  102. //            printf("%d %lld \n",rupc[i],rupc7[i]);
  103. //        }
  104.         //printf("1\n");
  105.         while(q--)
  106.         {
  107.             c=getchar();
  108.             c=getchar();
  109.           cin>>i;///  sd(i);
  110.             d=getchar();
  111.             d=getchar();
  112.                if(c=='=')
  113.             {
  114.                 l=0;up=j;k=0;
  115.                 while(l<=up)
  116.                 {m=(l+up)/2;
  117.                     if(rupc[m]==i)
  118.                     {if(m==0){k=rupc7[0];
  119.                             } else{k=rupc7[m]-rupc7[m-1];
  120.                         }    
  121.                         break; }
  122.                     if(rupc[m]<i)
  123.                        { l=m+1;
  124.                        }
  125.                     else{up=m-1;
  126.                         } } }
  127.            else  if(c=='<')
  128.             {
  129.                 if(rupc[0]>=i)
  130.                     k=0;
  131.                 else if(rupc[j]<i)
  132.                     k=rupc7[j];
  133.                 else
  134.                 { l=0; up=j;
  135.                     while(l<=up)
  136.                     {m=(l+up)/2;
  137.                         if(rupc[m]<i&&rupc[m+1]>=i)
  138.                         { k=rupc7[m];
  139.                             break;}
  140.                         if(rupc[m]<i)
  141.                           {  l=m+1;
  142.                           }
  143.                         else
  144.                            { up=m-1;
  145.                            }
  146.                     }
  147.                 }
  148.  
  149.             }
  150.  
  151.             else if (c=='>')
  152.             {if(rupc[0]>i)
  153.                    { k=rupc7[j];
  154.                    }
  155.                 else if(rupc[j]<=i)
  156.                    { k=0;
  157.                    }
  158.                 else
  159.                 { l=0;up=j; while(l<=up)
  160.                     {m=(l+up)/2;
  161.                         if(rupc[m]>i&&rupc[m-1]<=i)
  162.                         { k=rupc7[j]-rupc7[m-1];
  163.                             break; }
  164.                         if(rupc[m]<=i)
  165.                             {	l=m+1; }
  166.                         else{up=m-1;
  167.                         }}}
  168.             }
  169.             if(k%2==1)
  170.                  {   printf("%c",d);
  171.                  }
  172.             else
  173.             {
  174.                 if(d=='C')
  175.                   cout<<"D";///  printf("D");
  176.                 else
  177.                    cout<<"C";
  178.             }
  179.             //printf("%d\n",k);
  180.         }
  181.     return 0;
  182. }
  183. bool check(ass hole ,ass boobs){ return hole.x<boobs.x;}
  184. void make(it xxx,it l,it r)
  185. {
  186.     if(l>r)
  187.         return;
  188.     if(l==r)
  189.     {
  190.         forest[xxx]=rupc[r];
  191.         return;
  192.     }
  193.     make(xxx*2,l,(l+r)/2);
  194.     make(xxx*2+1,1+(l+r)/2,r);
  195.     forest[xxx]=max(forest[xxx*2],forest[xxx*2+1]);
  196. }
  197. it supckboobs(it xxx,it l,it r,it nip,it x)
  198. {
  199.     if(l>r||r<x||l>x)
  200.         return x;
  201.     if(r>=x&&l<=x)
  202.     {
  203.         if(forest[xxx]<=nip)
  204.         {
  205.             if(r<n-1){
  206.             if(rupc[r+1]>nip)
  207.                 return r;
  208.             return supckboobs(1,0,n-1,nip,r+1);}
  209.             return r;
  210.         }
  211.     }
  212.     if(l==r)
  213.        { return x;
  214.        }
  215.     it hoo=supckboobs(xxx*2,l,(l+r)/2,nip,x);
  216.     it haa=supckboobs(xxx*2+1,(l+r)/2 +1,r,nip,x);
  217.     return max(hoo,haa);
  218. }
  219. it supckdick(it xxx,it l,it r,it nip,it x)
  220. {
  221.     if(l>r||r<x||l>x)
  222.         return x;
  223.     if(r>=x)
  224.     {
  225.        if(l<=x) 
  226. 	   {if(forest[xxx]<nip)
  227.         {
  228.             if(l>0){
  229.             if(rupc[l-1]>=nip)
  230.                 return l;
  231.             return supckdick(1,0,n-1,nip,l-1);}
  232.             return l;
  233.         }
  234. 	   }
  235.     }
  236.     if(l==r&&l!=x)
  237.         return x;
  238.     if(x>0){
  239.         if(rupc[x-1]>=nip)
  240.             return x;
  241.     return supckdick(1,0,n-1,nip,x-1);}
  242.     it hoo=supckdick(xxx*2,l,(l+r)/2,nip,x);
  243.     it haa=supckdick(xxx*2+1,(l+r)/2 +1,r,nip,x);
  244.     return min(hoo,haa);
  245. }
  246.  
Success #stdin #stdout 0.01s 7644KB
comments (?)
stdin
copy 
main()

{printf("Bazinga!");

main();}
stdout
copy 
Standard output is empty
https://ideone.com/2TiGXG
language:
C++14 (gcc 8.3)
created:
1 year 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!