#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 200055;
struct SEG {
int d[MAXN*3], dc[MAXN*3];
void cal(int i, int s, int e) {
if(dc[i]) {
d[i] = e-s+1;
return;
}
if(s == e) {
d[i] = 0;
return;
}
d[i] = d[i<<1] + d[i<<1|1];
}
void upd(int i, int s, int e, int p, int q, int r) {
if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
dc[i] += r;
cal(i, s, e);
return;
}
int m = (s+e) >> 1;
upd(i<<1, s, m, p, q, r);
upd(i<<1|1, m+1, e, p, q, r);
cal(i, s, e);
}
int get() { return d[1]; }
} seg;
struct EVT {
EVT(int s, int p, int q, int r) : s(s), p(p), q(q), r(r) {}
int s, p, q, r;
bool operator < (const EVT &t) const {
return s < t.s;
}
};
vector<int> B[MAXN];
int A[MAXN];
int T, N, K;
void run() {
cin >> N;
for(int i = 1; i <= N; i++) cin >> A[i];
{
vector<int> V;
for(int i = 1; i <= N; i++) V.eb(A[i]);
sorv(V); univ(V);
for(int i = 1; i <= N; i++)
A[i] = int(lower_bound(allv(V), A[i]) - V.begin()) + 1;
K = sz(V);
}
for(int i = 1; i <= N; i++) B[A[i]].eb(i);
vector<EVT> EV;
for(int i = 1; i <= K; i++) {
auto &V = B[i];
int n = sz(V);
for(int i = 0; i < n; i++) {
int xs = i ? V[i-1]+1 : 1, x = V[i], xe = i+1 < n ? V[i+1]-1 : N;
EV.eb(xs, x, xe, 1);
EV.eb(x+1, x, xe, -1);
}
V.clear();
}
sorv(EV);
bool ans = false;
for(int x = 1, evi = 0, evn = sz(EV); x <= N; x++) {
for(; evi < evn && EV[evi].s == x; evi++)
seg.upd(1, 1, N, EV[evi].p, EV[evi].q, EV[evi].r);
if(seg.get() < N-x+1) {
ans = true;
}
}
puts(ans ? "boring" : "non-boring");
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for(cin >> T; T--;) run();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
201 ms |
6136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
