Submission #138461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138461	2019-07-30T04:16:37 Z	윤교준(#3320)	Non-boring sequences (CERC12_D)	C++14	1 / 1	1440 ms	30320 KB

D

#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+1; 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;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	5868 KB	Output is correct
2	Correct	430 ms	16376 KB	Output is correct
3	Correct	579 ms	30320 KB	Output is correct
4	Correct	328 ms	27788 KB	Output is correct
5	Correct	1440 ms	27576 KB	Output is correct
6	Correct	1169 ms	26800 KB	Output is correct
7	Correct	944 ms	26752 KB	Output is correct