QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649022#5466. Permutation Compressionhei_yu_baiAC ✓184ms58576kbC++203.3kb2024-10-17 21:19:032024-10-17 21:19:03

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 21:19:03]
  • 评测
  • 测评结果:AC
  • 用时:184ms
  • 内存:58576kb
  • [2024-10-17 21:19:03]
  • 提交

answer

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<numeric>

vector<int> bit;

void update(int p) {
	for (int i = p; i < bit.size(); i += i & -i) {
		bit[i]++;
	}
}

int getsum(int p) {
	int sum = 0;
	for (int i = p; i > 0; i -= i & -i) {
		sum += bit[i];
	}
	return sum;
}

int getsum(int l, int r) {
	return getsum(r) - getsum(l - 1);
}

const int N = 2e5 + 10;
vector<int> Log(N);

void init() {
	for (int i = 2; i < N; ++i) {
		Log[i] = Log[i >> 1] + 1;
	}
	return;
}

vector<vector<int>> st;
int tag;

void build(vector<int>& t) {
	int n = t.size(), logn = Log[n];
	st.assign(n, vector<int>(logn + 1));
	//tag = Log[n - 1];

	for (int i = 0; i < n; ++i) st[i][0] = t[i];
	for (int i = 1; i <= logn; ++i) {
		int d = 1 << (i - 1);
		for (int j = 1; j + (1 << i) - 1 < n; ++j) {
			st[j][i] = max(st[j][i - 1], st[j + d][i - 1]);
		}
	}

	return;
}

int query(int l, int r) {
	int L = Log[r - l + 1];
	return max(st[l][L], st[r - (1 << L) + 1][L]);
}

template<class T>
struct ST
{
	std::vector<std::vector<T>> f;

	ST(std::vector<T>& a)
	{
		int n = a.size(), logn = std::__lg(n);
		f.assign(n, std::vector<T>(logn + 1));

		for (int i = 0; i < n; i++) f[i][0] = a[i];
		for (int j = 0; j < logn; j++)
			for (int i = 0; i + (1 << (j + 1)) - 1 < n; i++)
				f[i][j + 1] = std::max(f[i][j], f[i + (1 << j)][j]);
	}

	T operator()(int l, int r) // [l, r)
	{
		int log = std::__lg(r - l);
		return std::max(f[l][log], f[r - (1 << log)][log]);
	}
};

void solve() {
	int n, m, k;
	cin >> n >> m >> k;

	bit.resize(n + 1);
	vector<int> a(n + 1), b(m + 1), p(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
		bit[i] = 0;
	}
	for (int i = 1; i <= m; ++i) cin >> b[i];

	multiset<int> s;
	s.insert(0);
	for (int i = 1; i <= k; ++i) {
		int v = 0;
		cin >> v;
		s.insert(v);
	}

	if (k < n - m) {
		cout << "NO\n";
		return;
	}

	int tp = 1;
	for (int i = 1; i <= m; ++i) {
		while (tp <= n && a[tp] != b[i]) ++tp;
	}

	if (tp == n + 1) {
		cout << "NO\n";
		return;
	}

	vector<bool> vis(n + 1);
	vector<int> t(n + 1);
	for (int i = 1; i <= m; ++i) {
		vis[b[i]] = true;
		t[p[b[i]]] = b[i];
	}

	ST<int> st(t);
	build(t);

	vector<int> l(n + 1), r(n + 1);
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			int tl = 0, tr = p[i];
			while (tl + 1 < tr) {
				int mid = (tl + tr) >> 1;
				(query(mid, p[i]) > i ? tl : tr) = mid;
			}
			l[p[i]] = tl;

			tl = p[i], tr = n + 1;
			while (tl + 1 < tr) {
				int mid = (tl + tr) >> 1;
				(query(p[i], mid) > i ? tr : tl) = mid;
			}
			r[p[i]] = tr;

			//cout << p[i] << " " << l[p[i]] << " " << r[p[i]] << "\n";
		}
	}

	for (int i = n; i > 0; --i) {
		if (!vis[i]) {
			int j = p[i];
			int q = getsum(l[j] + 1, r[j] - 1);
			//cout << r[j] << " " << l[j] << " " << q << " " << r[j] - l[j] - 1 - q << "\n";
			multiset<int>::iterator t = prev(s.upper_bound(r[j] - l[j] - 1 - q));
			if (t == s.begin()) {
				cout << "NO\n";
				return;
			}
			s.erase(t);
			update(j);
		}
	}

	cout << "YES\n";
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	init();

	int t = 1;
	cin >> t;
	while (t--) solve();

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3880kb

input:

3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

100
2 1 2
2 1
2
1 1
2 1 2
1 2
1
2 2
2 1 1
1 2
1
2
6 1 5
3 4 2 5 6 1
3
5 2 1 1 1
6 1 6
2 1 3 6 4 5
1
4 1 2 2 1 4
3 3 2
2 1 3
2 1 3
2 2
1 1 1
1
1
1
1 1 1
1
1
1
2 1 2
2 1
2
1 2
4 4 3
2 1 3 4
2 1 3 4
4 3 1
1 1 1
1
1
1
6 5 1
6 2 5 4 3 1
6 2 4 3 1
4
1 1 1
1
1
1
6 5 3
3 6 1 4 5 2
3 6 1 4 2
3 3 4
4 3 4
3 4 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YE...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

99
6 1 6
1 5 3 4 2 6
1
1 2 1 1 1 6
1 1 1
1
1
1
4 1 3
3 4 1 2
1
1 1 2
2 2 1
2 1
2 1
2
1 1 1
1
1
1
2 1 2
1 2
2
1 2
1 1 1
1
1
1
1 1 1
1
1
1
3 2 2
3 2 1
2 1
1 2
3 3 1
2 3 1
2 3 1
1
6 1 5
3 4 2 5 6 1
3
4 2 1 1 1
6 4 4
1 6 5 2 3 4
1 2 3 4
5 4 4 6
2 1 1
1 2
1
1
6 5 1
2 1 4 5 6 3
2 1 4 6 3
2
6 3 6
5 6 2 1 3...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YE...

result:

ok 99 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

98
6 1 6
6 1 4 5 2 3
3
1 2 2 1 1 6
4 3 2
2 3 4 1
2 1 3
3 4
1 1 1
1
1
1
6 1 6
6 4 3 1 2 5
1
3 1 3 1 1 5
1 1 1
1
1
1
6 4 4
3 4 1 2 5 6
3 4 1 2
2 4 3 1
6 5 1
4 5 3 6 1 2
4 5 3 1 2
6
1 1 1
1
1
1
5 1 4
1 3 2 4 5
1
5 3 4 4
6 3 4
1 4 2 3 6 5
1 2 5
5 4 6 5
4 1 3
2 1 4 3
2
1 1 1
1 1 1
1
1
1
6 3 5
5 1 3 6 4 2...

output:

YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
Y...

result:

ok 98 lines

Test #5:

score: 0
Accepted
time: 41ms
memory: 3856kb

input:

60000
1 1 1
1
1
1
1 1 1
1
1
1
3 2 1
2 3 1
2 1
2
3 3 1
1 2 3
1 2 3
1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 3 2
3 2 1
3 2 1
1 1
2 2 1
2 1
2 1
1
1 1 1
1
1
1
2 2 1
1 2
1 2
1
1 1 1
1
1
1
3 1 3
2 3 1
1
2 3 2
3 3 2
2 3 1
2 3 1
2 1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 2 3
3 2 1
2 1
1 2 1
3 2 2
1 3 2
3 2
3 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES...

result:

ok 60000 lines

Test #6:

score: 0
Accepted
time: 39ms
memory: 3888kb

input:

50000
1 1 1
1
1
1
4 3 4
1 2 3 4
1 2 3
2 3 4 4
1 1 1
1
1
1
3 2 1
3 1 2
1 2
3
4 1 4
2 1 4 3
2
4 4 3 4
3 1 2
1 2 3
2
3 3
4 1 3
4 2 1 3
1
3 2 4
4 4 2
4 1 2 3
4 1 2 3
3 4
3 1 2
2 1 3
3
1 3
4 2 2
4 3 1 2
3 1
2 1
1 1 1
1
1
1
4 3 1
1 2 3 4
1 2 4
4
4 1 4
4 3 2 1
4
2 1 1 2
3 3 1
2 1 3
2 1 3
1
4 3 2
1 3 2 4
1 ...

output:

YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
Y...

result:

ok 50000 lines

Test #7:

score: 0
Accepted
time: 36ms
memory: 3792kb

input:

40000
3 2 1
3 2 1
2 1
3
5 5 1
5 2 1 3 4
5 2 1 3 4
5
4 1 3
1 4 3 2
1
1 1 1
5 3 3
5 3 4 1 2
3 1 2
1 2 1
3 1 2
1 3 2
1
3 1
2 2 2
1 2
1 2
2 2
5 4 2
5 4 2 1 3
4 2 1 3
1 2
1 1 1
1
1
1
3 1 2
1 2 3
1
2 1
2 1 1
1 2
1
2
5 5 2
5 2 3 1 4
5 2 3 1 4
1 1
5 3 4
4 5 1 2 3
4 2 3
1 1 1 3
1 1 1
1
1
1
5 4 2
2 1 4 5 3
2 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
...

result:

ok 40000 lines

Test #8:

score: 0
Accepted
time: 35ms
memory: 3888kb

input:

40000
6 3 5
3 6 2 5 1 4
3 2 1
1 2 3 6 1
4 3 1
1 3 4 2
1 3 2
1
1 1 1
1
1
1
1 1 1
1
1
1
6 2 6
4 1 3 2 6 5
2 5
6 5 5 3 5 5
6 6 2
3 6 2 5 1 4
3 6 2 5 1 4
6 4
2 2 1
1 2
1 2
2
2 2 1
1 2
1 2
1
3 3 3
2 1 3
2 1 3
2 3 1
6 4 5
5 1 3 4 6 2
5 1 3 2
5 5 4 3 4
6 2 4
4 3 5 6 2 1
4 3
2 2 1 1
3 1 2
2 3 1
1
2 2
3 3 1
...

output:

YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YE...

result:

ok 40000 lines

Test #9:

score: 0
Accepted
time: 41ms
memory: 3960kb

input:

40000
7 5 2
6 4 2 1 3 5 7
6 4 2 1 3
3 1
2 2 2
2 1
2 1
1 1
4 1 4
3 4 2 1
1
3 4 2 1
3 2 2
1 3 2
1 2
1 3
5 2 4
4 3 2 5 1
2 1
2 2 2 5
7 1 7
2 7 5 6 1 4 3
3
3 3 1 1 3 1 6
7 7 2
3 7 2 5 1 6 4
3 7 2 5 1 6 4
5 6
6 2 6
2 6 3 4 1 5
2 1
6 3 4 5 3 5
3 1 3
3 1 2
1
2 3 3
7 5 3
1 7 5 4 6 3 2
5 4 6 3 2
6 1 1
6 3 5
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
YES
YES
...

result:

ok 40000 lines

Test #10:

score: 0
Accepted
time: 43ms
memory: 3808kb

input:

40000
4 2 4
4 1 3 2
4 2
3 4 4 3
6 3 5
6 2 4 5 1 3
2 1 3
1 1 2 6 1
8 5 6
1 7 2 8 6 5 3 4
1 7 5 2 3
3 1 2 8 7 8
6 6 1
3 4 6 1 5 2
3 4 6 1 5 2
6
8 7 2
6 8 5 7 1 3 2 4
6 5 7 1 3 2 4
8 7
1 1 1
1
1
1
4 3 3
2 4 3 1
2 4 3
1 2 4
4 3 3
1 3 4 2
1 3 2
4 4 3
2 2 1
1 2
1 2
2
7 5 3
5 2 3 7 1 6 4
2 3 1 6 4
7 5 6
7 ...

output:

NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO...

result:

ok 40000 lines

Test #11:

score: 0
Accepted
time: 45ms
memory: 3668kb

input:

40000
2 2 2
1 2
1 2
1 1
8 2 6
1 3 5 4 6 7 2 8
3 2
2 8 6 8 7 8
8 5 4
3 1 2 7 8 5 4 6
3 1 2 5 4
8 7 7 7
1 1 1
1
1
1
1 1 1
1
1
1
2 1 1
1 2
2
2
2 2 2
1 2
2 1
2 2
2 2 2
2 1
2 1
2 1
8 1 7
5 3 8 4 1 7 6 2
2
3 5 2 1 1 1 1
9 8 2
7 8 1 6 4 5 9 3 2
7 8 1 6 4 5 3 2
2 9
2 1 2
2 1
2
1 1
4 1 4
3 1 4 2
3
1 2 1 2
3 ...

output:

YES
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES...

result:

ok 40000 lines

Test #12:

score: 0
Accepted
time: 43ms
memory: 3832kb

input:

40000
1 1 1
1
1
1
7 5 4
7 4 6 2 5 1 3
7 4 6 2 1
1 2 3 7
7 4 3
7 4 1 3 2 5 6
1 3 2 5
6 5 7
7 1 6
5 4 3 1 7 2 6
6
4 2 3 1 1 1
4 3 4
2 4 3 1
2 3 1
2 3 3 3
3 1 3
3 1 2
2
1 3 3
1 1 1
1
1
1
2 1 1
1 2
1
2
9 2 8
9 8 6 4 2 1 5 7 3
4 1
1 2 2 3 5 4 2 9
1 1 1
1
1
1
4 2 3
2 4 3 1
2 1
3 2 4
3 3 3
1 3 2
1 3 2
3 3 ...

output:

YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YE...

result:

ok 40000 lines

Test #13:

score: 0
Accepted
time: 47ms
memory: 3908kb

input:

40000
6 3 5
4 3 2 5 1 6
2 3 1
2 1 1 6 6
2 1 1
1 2
1
1
6 5 4
1 3 5 6 2 4
1 3 6 2 4
2 2 6 6
8 2 7
5 8 4 7 1 3 2 6
6 2
1 3 1 1 1 1 7
1 1 1
1
1
1
11 6 5
2 4 11 6 9 3 8 1 7 5 10
2 4 3 6 8 5
3 1 4 1 1
8 3 8
6 4 8 5 1 3 7 2
4 1 2
2 2 1 3 3 4 8 4
2 1 2
2 1
1
2 2
5 5 1
1 5 3 4 2
1 5 3 4 2
5
9 2 9
8 7 5 6 2 4...

output:

NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES...

result:

ok 40000 lines

Test #14:

score: 0
Accepted
time: 44ms
memory: 3896kb

input:

40000
5 4 3
1 5 4 2 3
1 4 2 3
1 5 4
12 1 12
8 11 5 1 7 3 10 6 4 9 12 2
4
3 6 2 1 1 2 9 11 12 10 11 12
2 2 1
2 1
2 1
2
4 3 4
2 3 4 1
2 3 1
2 2 1 3
2 2 1
2 1
2 1
2
6 4 5
2 5 3 4 1 6
2 3 1 6
3 6 6 3 6
4 4 1
3 4 1 2
3 4 1 2
2
3 1 2
3 2 1
1
3 3
11 8 4
11 3 10 5 1 6 4 8 7 9 2
11 3 1 6 4 7 9 2
10 8 11 10
1...

output:

YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YE...

result:

ok 40000 lines

Test #15:

score: 0
Accepted
time: 18ms
memory: 3612kb

input:

10000
10 5 6
5 6 9 10 7 1 3 2 4 8
5 6 9 1 2
8 9 9 10 10 10
10 6 5
5 6 7 2 4 8 10 9 1 3
5 2 8 9 1 3
9 7 7 10 10
5 3 4
3 5 4 1 2
4 1 2
3 5 4 5
6 3 5
6 1 2 5 4 3
1 4 3
4 5 5 5 4
10 8 5
7 3 1 5 9 8 2 6 10 4
3 1 5 9 8 2 6 4
6 1 4 8 10
10 6 4
7 1 4 5 8 9 3 10 2 6
1 4 8 3 2 6
2 1 2 1
10 3 10
9 6 4 7 2 5 8 ...

output:

NO
NO
NO
NO
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES...

result:

ok 10000 lines

Test #16:

score: 0
Accepted
time: 25ms
memory: 3648kb

input:

10000
15 15 1
15 6 5 8 3 2 12 9 10 1 4 7 14 11 13
15 6 5 8 3 2 12 9 10 1 4 7 14 11 13
10
8 3 6
5 6 2 4 1 3 8 7
6 1 7
7 7 8 8 8 7
19 1 19
7 10 13 3 5 16 12 17 19 8 1 2 11 18 6 14 9 15 4
1
4 8 1 1 5 1 1 3 2 5 2 2 1 17 18 18 18 17 18
20 11 12
5 14 20 19 1 10 8 3 13 15 4 2 16 18 7 6 17 9 11 12
5 14 10 8...

output:

YES
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
Y...

result:

ok 10000 lines

Test #17:

score: 0
Accepted
time: 43ms
memory: 3820kb

input:

10000
4 3 4
1 4 3 2
1 3 2
2 4 3 4
1 1 1
1
1
1
79 70 9
73 34 21 66 52 46 72 32 63 44 48 11 77 40 15 51 50 67 70 53 62 3 31 69 20 41 28 30 54 10 7 19 24 74 5 4 59 1 18 37 68 25 23 58 6 33 65 55 43 39 17 12 49 35 56 8 75 64 45 14 36 22 13 57 60 27 71 61 42 9 76 2 16 79 78 26 38 47 29
73 34 21 66 52 46 ...

output:

YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
...

result:

ok 10000 lines

Test #18:

score: 0
Accepted
time: 77ms
memory: 19720kb

input:

10
10201 2518 7686
8039 7511 4669 4613 6162 1290 9288 8391 4993 2070 8427 2499 3018 4916 4911 6060 8440 8901 8250 8997 3347 142 4313 3070 4228 9879 9075 2665 5642 762 2855 9465 1799 10036 6353 2529 8827 686 3883 6577 1430 5052 8277 6025 3863 8054 2652 618 8088 8364 3502 7890 391 9096 8691 919 6628 5...

output:

NO
NO
YES
YES
YES
NO
YES
NO
YES
NO

result:

ok 10 lines

Test #19:

score: 0
Accepted
time: 73ms
memory: 12948kb

input:

20
3517 1806 1714
2427 3145 194 284 2676 2141 2910 1618 2873 1968 40 243 1537 1591 1601 2415 4 3510 2693 406 2190 1132 2469 2613 1250 779 922 1718 1695 2492 993 1755 401 2836 852 3047 2043 3222 894 2147 694 648 3231 3218 1357 1075 1493 2303 9 1948 2212 2702 1547 2074 2697 158 686 3377 580 561 3256 2...

output:

NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO

result:

ok 20 lines

Test #20:

score: 0
Accepted
time: 54ms
memory: 9060kb

input:

30
15323 12316 3009
5461 8905 8847 12520 7056 5196 2078 6413 10193 12294 4601 3990 3691 6826 1631 4736 1507 5339 9776 3413 3135 4489 6794 9471 862 9813 7867 1310 6835 13073 14303 6260 7845 1433 619 4653 10981 8986 4105 5834 14974 7877 11174 14863 3485 4000 5318 3431 9158 14662 4199 13232 11276 6580 ...

output:

YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
NO
YES

result:

ok 30 lines

Test #21:

score: 0
Accepted
time: 132ms
memory: 36692kb

input:

3
123075 23064 100012
93912 55885 25582 39571 6971 36425 111197 79711 41681 36088 693 117681 100171 12244 42071 77370 19600 53711 112897 110126 115034 42792 46276 8459 72493 52952 122924 83906 367 41855 74275 99613 118996 21890 122972 36973 76603 40716 7063 79518 4540 39960 38554 55233 19544 92392 3...

output:

NO
YES
NO

result:

ok 3 lines

Test #22:

score: 0
Accepted
time: 115ms
memory: 34804kb

input:

4
31527 2796 28734
1091 15861 5182 25030 27184 384 25626 7875 22836 23990 4973 27139 12878 30083 11749 20745 3399 19106 29421 12483 20464 30788 19048 29417 24523 22999 25196 28530 27888 26709 3478 19015 24185 887 1969 2215 24685 15962 18456 23338 18736 4527 22655 4687 23060 11863 4901 3527 7811 2283...

output:

NO
NO
YES
NO

result:

ok 4 lines

Test #23:

score: 0
Accepted
time: 133ms
memory: 38512kb

input:

5
128749 17051 111701
42741 35862 99499 45249 15779 49403 94479 13369 26628 74005 104652 61098 74718 101311 121179 35971 17170 127737 44876 86156 37900 121074 59776 8186 33056 70308 47231 103130 46819 30793 92983 64947 81070 22509 81368 63589 93078 4151 100180 73376 98264 107502 11904 38860 21961 10...

output:

YES
NO
YES
NO
NO

result:

ok 5 lines

Test #24:

score: 0
Accepted
time: 145ms
memory: 56352kb

input:

1
200000 57269 142732
56485 21830 54745 11490 20478 59868 167162 157180 123880 143389 44431 140207 54973 40039 150219 159643 85985 14685 3473 102446 6810 92845 180268 114911 137969 132109 128664 108792 186933 55472 195896 115087 15917 105577 65383 70698 113367 65049 2997 160394 11175 198245 185075 1...

output:

YES

result:

ok single line: 'YES'

Test #25:

score: 0
Accepted
time: 116ms
memory: 53564kb

input:

1
199999 120008 79991
11524 59564 34585 129380 105753 63181 176751 119041 169055 186005 190477 79671 1720 193902 143991 198305 69536 183827 3714 110965 179278 149649 71533 182722 75184 138062 181285 93178 86162 133827 125972 129063 45913 64540 162821 124187 36375 64939 134935 148193 102682 100111 18...

output:

NO

result:

ok single line: 'NO'

Test #26:

score: 0
Accepted
time: 164ms
memory: 58196kb

input:

1
199998 12889 187112
54885 81539 162891 84489 130233 4096 3799 9829 21054 167111 154545 36547 37796 75620 65489 157435 113420 89616 184076 35797 127006 198125 41743 86532 149556 96068 39239 89854 33860 4724 12003 189987 173261 172025 164487 73735 89862 144539 3988 130032 129552 179986 14001 24747 1...

output:

YES

result:

ok single line: 'YES'

Test #27:

score: 0
Accepted
time: 85ms
memory: 52032kb

input:

1
199997 153139 46858
183204 93470 24352 15732 37436 10974 170128 170089 74009 79847 56162 103302 17084 154007 75065 171213 1153 148087 50102 51955 177246 20666 4212 51145 165520 56719 7671 163117 78613 110765 154097 170382 104314 48488 108419 9810 185722 163443 135931 190348 42275 199252 180289 245...

output:

YES

result:

ok single line: 'YES'

Test #28:

score: 0
Accepted
time: 121ms
memory: 54964kb

input:

1
199996 86158 113838
81446 101407 142912 106775 22395 111854 111586 41927 13570 92769 33003 48836 161914 196696 45540 99175 124555 52273 110429 53625 102678 53933 195706 23936 163148 86968 18878 175728 19332 160549 104907 24741 2395 195686 170166 110638 9285 25328 23058 5167 104793 137648 149623 10...

output:

NO

result:

ok single line: 'NO'

Test #29:

score: 0
Accepted
time: 142ms
memory: 55892kb

input:

1
199995 66973 133022
141540 128289 167404 140394 4021 105225 90743 154484 126214 160784 83736 150642 296 68317 114500 67405 158794 37791 141 74145 58490 56256 25698 17061 133675 81700 187523 110730 78879 95692 149275 9442 13255 146084 155698 72731 126211 156427 16459 93208 43627 60181 101903 2339 2...

output:

NO

result:

ok single line: 'NO'

Test #30:

score: 0
Accepted
time: 114ms
memory: 54392kb

input:

1
199994 97123 102871
140014 28957 186661 19712 169590 65843 86042 4144 116297 132483 195845 145682 86370 122119 173093 117347 78762 85412 60300 62993 137507 165076 71161 58577 176802 144149 24309 101925 33453 39706 21387 79174 173927 194133 83446 88159 13 92186 174668 31779 141573 111747 2989 74690...

output:

YES

result:

ok single line: 'YES'

Test #31:

score: 0
Accepted
time: 106ms
memory: 54152kb

input:

1
199993 101458 98535
11612 139662 116573 168331 48474 76673 80313 135138 155730 73720 59045 199095 64703 168675 164136 23826 100378 164306 138852 7422 24299 110739 111786 147737 152865 107362 67755 116328 47436 131074 169135 140764 76351 146587 124128 106612 18428 168845 44079 31449 38004 18208 797...

output:

YES

result:

ok single line: 'YES'

Test #32:

score: 0
Accepted
time: 131ms
memory: 55556kb

input:

1
199992 73979 126014
35909 21472 152208 54748 186757 108976 87082 101782 136679 177796 197065 140053 75254 62673 107111 176089 142370 66404 17342 37124 165483 41098 167771 171447 30539 156680 14270 89595 56092 121834 98304 112092 16376 69358 70793 131338 190023 94738 33227 154099 171946 182215 1678...

output:

NO

result:

ok single line: 'NO'

Test #33:

score: 0
Accepted
time: 184ms
memory: 57528kb

input:

1
199991 24343 175649
153553 142394 186662 67981 195345 174639 23591 85769 5322 167939 73334 120872 184252 88372 51941 50879 47503 19563 6677 88427 126844 99875 127529 113644 69091 136866 106140 192681 6708 185233 25647 153904 159371 95971 51590 72802 27189 2727 157823 183992 29754 73757 134656 1697...

output:

NO

result:

ok single line: 'NO'

Test #34:

score: 0
Accepted
time: 182ms
memory: 58576kb

input:

1
199990 1388 198605
50975 121777 173124 95675 192142 2934 40114 8762 97502 151068 148937 158439 196125 115277 108436 162601 89008 147711 96892 78631 180569 4834 11769 12958 11585 135529 27035 162566 135359 194508 193810 45239 57541 88264 62357 13361 127923 112153 14597 74853 114074 44360 17793 2451...

output:

NO

result:

ok single line: 'NO'

Test #35:

score: 0
Accepted
time: 144ms
memory: 39516kb

input:

2
130110 4246 125865
99005 40961 121962 24580 66052 114670 26015 27641 107070 116566 87592 8602 41453 24897 33652 50896 104498 80408 127525 45573 92127 67860 60665 121884 26029 102328 25890 63677 106518 91202 78935 66173 57565 116088 125763 50178 56752 99451 128061 36800 65370 13537 54525 37577 5940...

output:

YES
YES

result:

ok 2 lines

Test #36:

score: 0
Accepted
time: 102ms
memory: 31240kb

input:

6
27635 22575 5062
27304 18052 17813 6163 20953 10639 22159 25729 20194 19702 13040 2574 27629 16849 11447 7173 702 16006 24377 16687 14594 14285 16770 23620 24389 27554 24480 10606 6738 16514 6117 4947 23856 17614 18656 15402 4588 26086 18881 9437 6072 1716 7400 19942 22334 468 4966 11530 14379 232...

output:

YES
NO
YES
YES
YES
YES

result:

ok 6 lines

Test #37:

score: 0
Accepted
time: 38ms
memory: 4332kb

input:

1000
28 4 27
24 16 26 1 14 25 2 6 8 3 22 10 5 15 18 27 21 4 11 17 7 23 28 9 20 19 12 13
1 2 6 13
24 20 6 2 15 6 7 2 14 5 2 1 8 3 5 7 1 1 2 1 5 1 2 1 5 24 16
45 37 10
35 17 23 32 7 38 43 6 3 16 26 41 18 44 5 20 4 22 9 33 24 14 28 10 21 1 11 12 42 37 39 29 8 25 15 30 31 2 36 27 40 45 13 34 19
35 17 23...

output:

YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
YES
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
NO
NO
NO
Y...

result:

ok 1000 lines

Test #38:

score: 0
Accepted
time: 26ms
memory: 4212kb

input:

1000
200 66 137
153 6 102 50 38 31 136 163 149 117 19 182 55 25 108 60 61 158 30 27 24 165 104 157 189 73 33 32 100 115 148 164 14 196 181 103 147 45 20 8 155 127 175 162 139 3 78 150 13 99 12 57 94 56 34 119 188 137 76 47 160 4 96 29 192 91 178 62 90 84 15 143 106 101 88 171 173 185 37 174 177 145 ...

output:

NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
YES
...

result:

ok 1000 lines

Test #39:

score: 0
Accepted
time: 50ms
memory: 4548kb

input:

1000
538 481 57
298 29 470 505 119 524 153 83 493 351 36 43 16 485 192 218 124 377 507 195 310 262 103 208 212 426 276 304 163 207 93 389 355 114 113 509 523 307 158 17 140 201 96 206 266 126 448 198 67 224 530 511 52 501 179 393 331 395 372 141 162 282 374 111 268 69 461 18 57 2 180 128 466 156 342...

output:

NO
NO
YES
NO
YES
NO
YES
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
...

result:

ok 1000 lines

Test #40:

score: 0
Accepted
time: 50ms
memory: 4332kb

input:

1000
137 106 34
6 65 96 23 64 130 21 8 102 7 107 18 49 128 79 116 69 98 119 88 72 66 122 15 43 94 60 11 39 14 28 120 113 51 126 30 89 121 47 82 2 80 77 17 33 52 84 104 45 111 34 93 50 13 68 112 37 105 24 27 129 109 86 91 134 115 103 75 136 101 12 123 63 76 108 73 48 4 137 87 58 67 38 3 125 41 127 85...

output:

NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
YES
YES
NO
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YE...

result:

ok 1000 lines

Test #41:

score: 0
Accepted
time: 30ms
memory: 9716kb

input:

1
200000 100000 65281
200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 19996...

output:

NO

result:

ok single line: 'NO'

Test #42:

score: 0
Accepted
time: 16ms
memory: 6828kb

input:

1
199999 99999 4722
199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 ...

output:

NO

result:

ok single line: 'NO'

Test #43:

score: 0
Accepted
time: 119ms
memory: 56516kb

input:

1
199998 99999 149007
199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 19995...

output:

YES

result:

ok single line: 'YES'

Test #44:

score: 0
Accepted
time: 93ms
memory: 55296kb

input:

1
199997 99998 114264
199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 199959 19995...

output:

YES

result:

ok single line: 'YES'

Test #45:

score: 0
Accepted
time: 120ms
memory: 58196kb

input:

1
199996 99998 177538
99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99...

output:

YES

result:

ok single line: 'YES'

Test #46:

score: 0
Accepted
time: 99ms
memory: 55196kb

input:

1
199995 99997 119337
99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 99...

output:

YES

result:

ok single line: 'YES'