Advertisement
anoosykh95

Untitled

Jul 22nd, 2016
371
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define P(x,y) make_pair(x,y)
  3. using namespace std;
  4. class Rectangle{
  5.     public:
  6.     int x1 , y1 , x2 , y2;
  7.     static Rectangle empt;
  8.     Rectangle(){
  9.         x1=y1=x2=y2=0;
  10.     }
  11.     Rectangle(int X1 , int Y1 , int X2 , int Y2){
  12.         x1 = X1; y1=Y1;
  13.         x2 = X2; y2=Y2;
  14.     }
  15.     Rectangle intersect(Rectangle R){
  16.         if(R.x1 > x2 || R.x2 < x1) return empt;
  17.         if(R.y1 > y2 || R.y2 < y1) return empt;
  18.         Rectangle ret =  Rectangle(max(x1 , R.x1) , max(y1 , R.y1) , min(x2 , R.x2) , min(y2 , R.y2));
  19.         return ret;
  20.     }
  21.     bool operator == (Rectangle R){
  22.         return (R.x1==x1)&&(R.y1==y1)&&(R.y2==y2)&&(R.x2==x2);
  23.     }
  24. };
  25. struct Event{
  26.     int x , y1 , y2 , type;
  27.     Event(){}
  28.     Event(int x , int y1 , int y2 , int type):x(x) , y1(y1) , y2(y2) , type(type){}
  29. };
  30. bool operator < (const Event&A , const Event&B){
  31.     //if(A.x != B.x)
  32.     if(A.x != B.x) return A.x < B.x;
  33.     else return A.type < B.type;
  34.     //if(A.y1 != B.y1) return A.y1 < B.y1;
  35.     //if(A.y2 != B.y2()) A.y2 < B.y2;
  36. }
  37. const int MX=(1<<20);
  38. struct Node{
  39.     int prob , sum , ans;
  40.     Node(){}
  41.     Node(int prob , int sum , int ans):prob(prob) , sum(sum) , ans(ans){}
  42. };
  43. Node tree[MX*4];
  44. int interval[MX];
  45. void build(int x , int a , int b){
  46.     tree[x] = Node(0 , 0 , 0);
  47.     if(a==b){
  48.         tree[x].sum+=interval[a];
  49.         return;
  50.     }
  51.     build(x*2 , a , (a+b)/2);
  52.     build(x*2+1 , (a+b)/2+1 , b);
  53.     tree[x].sum = tree[x*2].sum + tree[x*2+1].sum;
  54. }
  55. int ask(int x){
  56.     if(tree[x].prob) return tree[x].sum;
  57.     return tree[x].ans;
  58. }
  59. int st , en , V;
  60. void update(int x , int a , int b){
  61.     if(st>b || en<a) return;
  62.     if(a>=st && b<=en){
  63.         tree[x].prob+=V;
  64.         return;
  65.     }
  66.     update(x*2 , a , (a+b)/2);
  67.     update(x*2+1 , (a+b)/2+1 , b);
  68.     tree[x].ans = ask(x*2) + ask(x*2+1);
  69. }
  70. Rectangle Rectangle::empt = Rectangle();
  71. vector < Rectangle > Rect;
  72. vector < int > Start , End , sorted;
  73. vector < Event > sweep;
  74. void compressncalc(){
  75.     sweep.clear();
  76.     Start.clear();
  77.     End.clear();
  78.     sorted.clear();
  79.     for(auto R : Rect){
  80.         sorted.push_back(R.y1);
  81.         sorted.push_back(R.y2);
  82.     }
  83.     sort(sorted.begin() , sorted.end());
  84.     sorted.erase(unique(sorted.begin() , sorted.end()) , sorted.end());
  85.     int sz = sorted.size();
  86.     for(int j=0;j<sz;j++){
  87.         Start.push_back(sorted[j]);
  88.         End.push_back(sorted[j]);
  89.         if(j<sz-1 && sorted[j] != sorted[j+1] - 1){
  90.             Start.push_back(sorted[j]+1);
  91.             End.push_back(sorted[j+1]-1);
  92.         }
  93.     }
  94.     sz = Start.size();
  95.     for(int j=0;j<sz;j++)
  96.         interval[j+1] = End[j] - Start[j] + 1;
  97.     for(auto R : Rect){
  98.         sweep.push_back(Event(R.x1 , R.y1 , R.y2 , 1));
  99.         sweep.push_back(Event(R.x2+1 , R.y1 , R.y2 , -1));
  100.     }
  101.     sort(sweep.begin() , sweep.end());
  102.     build(1,1,sz);
  103. }
  104. long long ans;
  105. void Sweep(){
  106.     ans=0;
  107.     if(sorted.empty() || sweep.empty()) return;
  108.     int last = 0 , sz_ = Start.size();
  109.     for(int j=0;j<sweep.size();j++){
  110.         ans+= 1ll * (sweep[j].x - last) * ask(1);
  111.         last = sweep[j].x;
  112.         V = sweep[j].type;
  113.         st = lower_bound(Start.begin() , Start.end() , sweep[j].y1) - Start.begin() + 1;
  114.         en = lower_bound(End.begin() , End.end() , sweep[j].y2) - End.begin() + 1;
  115.         update(1 , 1 , sz_);
  116.     }
  117. }
  118. map < int , int > hashy;
  119. vector < int > v[MX];
  120. int n , arr[MX];
  121. int main(){
  122.     //freopen("in.in","r",stdin);
  123.     int T;scanf("%d",&T);
  124.     while(T--){
  125.         hashy.clear();
  126.         Rect.clear();
  127.         for(int j=1;j<=n;j++) v[j].clear();
  128.         scanf("%d",&n);
  129.         for(int j=1;j<=n;j++){
  130.             scanf("%d",&arr[j]);
  131.             hashy[arr[j]]=1;
  132.         }
  133.         int cc=0;
  134.         for(auto it : hashy) hashy[it.first] = ++cc;
  135.         for(int j=1;j<=cc;j++) v[j].push_back(0);
  136.         for(int j=1;j<=n;j++){
  137.             arr[j] = hashy[arr[j]];
  138.             v[arr[j]].push_back(j);
  139.         }
  140.         for(int j=1;j<=cc;j++) v[j].push_back(n+1);
  141.         for(int j=1;j<=cc;j++){
  142.             int sz = v[j].size();
  143.             for(int i=1;i<sz-1;i++)
  144.                 Rect.push_back(Rectangle(v[j][i-1]+1 , v[j][i] , v[j][i] , v[j][i+1]-1 ));
  145.         }
  146.         compressncalc();
  147.         Sweep();
  148.         if(ans == 1ll * n *(n+1) / 2)
  149.             puts("non-boring");
  150.         else puts("boring");
  151.  
  152.  
  153.     }
  154.  
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement