oj.uz

Submission #138472

# Submission time Handle Problem Language Result Execution time Memory
138472 2019-07-30T05:03:24 Z 임유진(#3321) Non-boring sequences (CERC12_D) C++14
1 / 1
 693 ms 7520 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int A[MAXN];
int nx[MAXN], pv[MAXN];
int as[MAXN];
int idx[MAXN];

bool boring(int s, int e) {
	priority_queue<int> mx, mxt;
	priority_queue<int, vector<int>, greater<int> > mn, mnt;
	
	//printf("boring(%d, %d)\n", s, e);
	for(int i = s; i <= e; i++) if(pv[i] < s && nx[i] > e) {
		mx.push(i);
		mn.push(i);
	}
	while(!mx.empty()) {
		if(mn.top() - s < e - mx.top()) {
			int t = mn.top();
			mn.pop();
			mxt.push(t);
			for(int i = s; i < t; i++) if(t < nx[i] && nx[i] <= e && nx[nx[i]] > e) {
				mn.push(nx[i]);
				mx.push(nx[i]);
			}
			if(boring(s, t - 1)) return true;
			s = t + 1;
		}
		else {
			int t = mx.top();
			mx.pop();
			mnt.push(t);
			for(int i = t + 1; i <= e; i++) if(s <= pv[i] && pv[i] < t && pv[pv[i]] < s) {
				mn.push(pv[i]);
				mx.push(pv[i]);
			}
			if(boring(t + 1, e)) return true;
			e = t - 1;
		}
		while(!mxt.empty() && mx.top() == mxt.top()) {
			mx.pop();
			mxt.pop();
		}
		while(!mnt.empty() && mn.top() == mnt.top()) {
			mn.pop();
			mnt.pop();
		}
	}
	return s <= e;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T;
	
	cin >> T;
	while(T--) {
		//printf("*\n");
		int N;
		cin >> N;
		for(int i = 0; i < N; i++) cin >> A[i];
		for(int i = 0; i < N; i++) as[i] = A[i];
		sort(as, as + N);
		for(int i = 0; i < N; i++) A[i] = lower_bound(as, as + N, A[i]) - as;
		for(int i = 0; i < N; i++) {
			idx[i] = -1;
			nx[i] = N;
		}
		for(int i = 0; i < N; i++) {
			if(idx[A[i]] != -1) nx[idx[A[i]]] = i;
			pv[i] = idx[A[i]];
			idx[A[i]] = i;
		}
		//for(int i = 0; i < N; i++) printf("(%d, %d) ", pv[i], nx[i]);
		//printf("\n");
		if(boring(0, N - 1)) cout << "boring\n";
		else cout << "non-boring\n";
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1144 KB Output is correct
2 Correct 214 ms 2948 KB Output is correct
3 Correct 283 ms 7520 KB Output is correct
4 Correct 190 ms 5528 KB Output is correct
5 Correct 693 ms 5212 KB Output is correct
6 Correct 604 ms 4448 KB Output is correct
7 Correct 468 ms 4300 KB Output is correct