Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define P(x,y) make_pair(x,y)
- using namespace std;
- class Rectangle{
- public:
- int x1 , y1 , x2 , y2;
- static Rectangle empt;
- Rectangle(){
- x1=y1=x2=y2=0;
- }
- Rectangle(int X1 , int Y1 , int X2 , int Y2){
- x1 = X1; y1=Y1;
- x2 = X2; y2=Y2;
- }
- Rectangle intersect(Rectangle R){
- if(R.x1 > x2 || R.x2 < x1) return empt;
- if(R.y1 > y2 || R.y2 < y1) return empt;
- Rectangle ret = Rectangle(max(x1 , R.x1) , max(y1 , R.y1) , min(x2 , R.x2) , min(y2 , R.y2));
- return ret;
- }
- bool operator == (Rectangle R){
- return (R.x1==x1)&&(R.y1==y1)&&(R.y2==y2)&&(R.x2==x2);
- }
- };
- struct Event{
- int x , y1 , y2 , type;
- Event(){}
- Event(int x , int y1 , int y2 , int type):x(x) , y1(y1) , y2(y2) , type(type){}
- };
- bool operator < (const Event&A , const Event&B){
- //if(A.x != B.x)
- if(A.x != B.x) return A.x < B.x;
- else return A.type < B.type;
- //if(A.y1 != B.y1) return A.y1 < B.y1;
- //if(A.y2 != B.y2()) A.y2 < B.y2;
- }
- const int MX=(1<<20);
- struct Node{
- int prob , sum , ans;
- Node(){}
- Node(int prob , int sum , int ans):prob(prob) , sum(sum) , ans(ans){}
- };
- Node tree[MX*4];
- int interval[MX];
- void build(int x , int a , int b){
- tree[x] = Node(0 , 0 , 0);
- if(a==b){
- tree[x].sum+=interval[a];
- return;
- }
- build(x*2 , a , (a+b)/2);
- build(x*2+1 , (a+b)/2+1 , b);
- tree[x].sum = tree[x*2].sum + tree[x*2+1].sum;
- }
- int ask(int x){
- if(tree[x].prob) return tree[x].sum;
- return tree[x].ans;
- }
- int st , en , V;
- void update(int x , int a , int b){
- if(st>b || en<a) return;
- if(a>=st && b<=en){
- tree[x].prob+=V;
- return;
- }
- update(x*2 , a , (a+b)/2);
- update(x*2+1 , (a+b)/2+1 , b);
- tree[x].ans = ask(x*2) + ask(x*2+1);
- }
- Rectangle Rectangle::empt = Rectangle();
- vector < Rectangle > Rect;
- vector < int > Start , End , sorted;
- vector < Event > sweep;
- void compressncalc(){
- sweep.clear();
- Start.clear();
- End.clear();
- sorted.clear();
- for(auto R : Rect){
- sorted.push_back(R.y1);
- sorted.push_back(R.y2);
- }
- sort(sorted.begin() , sorted.end());
- sorted.erase(unique(sorted.begin() , sorted.end()) , sorted.end());
- int sz = sorted.size();
- for(int j=0;j<sz;j++){
- Start.push_back(sorted[j]);
- End.push_back(sorted[j]);
- if(j<sz-1 && sorted[j] != sorted[j+1] - 1){
- Start.push_back(sorted[j]+1);
- End.push_back(sorted[j+1]-1);
- }
- }
- sz = Start.size();
- for(int j=0;j<sz;j++)
- interval[j+1] = End[j] - Start[j] + 1;
- for(auto R : Rect){
- sweep.push_back(Event(R.x1 , R.y1 , R.y2 , 1));
- sweep.push_back(Event(R.x2+1 , R.y1 , R.y2 , -1));
- }
- sort(sweep.begin() , sweep.end());
- build(1,1,sz);
- }
- long long ans;
- void Sweep(){
- ans=0;
- if(sorted.empty() || sweep.empty()) return;
- int last = 0 , sz_ = Start.size();
- for(int j=0;j<sweep.size();j++){
- ans+= 1ll * (sweep[j].x - last) * ask(1);
- last = sweep[j].x;
- V = sweep[j].type;
- st = lower_bound(Start.begin() , Start.end() , sweep[j].y1) - Start.begin() + 1;
- en = lower_bound(End.begin() , End.end() , sweep[j].y2) - End.begin() + 1;
- update(1 , 1 , sz_);
- }
- }
- map < int , int > hashy;
- vector < int > v[MX];
- int n , arr[MX];
- int main(){
- //freopen("in.in","r",stdin);
- int T;scanf("%d",&T);
- while(T--){
- hashy.clear();
- Rect.clear();
- for(int j=1;j<=n;j++) v[j].clear();
- scanf("%d",&n);
- for(int j=1;j<=n;j++){
- scanf("%d",&arr[j]);
- hashy[arr[j]]=1;
- }
- int cc=0;
- for(auto it : hashy) hashy[it.first] = ++cc;
- for(int j=1;j<=cc;j++) v[j].push_back(0);
- for(int j=1;j<=n;j++){
- arr[j] = hashy[arr[j]];
- v[arr[j]].push_back(j);
- }
- for(int j=1;j<=cc;j++) v[j].push_back(n+1);
- for(int j=1;j<=cc;j++){
- int sz = v[j].size();
- for(int i=1;i<sz-1;i++)
- Rect.push_back(Rectangle(v[j][i-1]+1 , v[j][i] , v[j][i] , v[j][i+1]-1 ));
- }
- compressncalc();
- Sweep();
- if(ans == 1ll * n *(n+1) / 2)
- puts("non-boring");
- else puts("boring");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement