Submission #1099654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099654		Math4Life2020	Alternating Heights (CCO22_day1problem1)	C++17	0 / 25	348 ms	12880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 3005;
ll N;
ll a[Nm];
ll ans[Nm];

bool qry(ll x, ll y) {
	ll tfound[N];
	for (ll i=0;i<N;i++) {
		tfound[i]=-1;
	}
	vector<ll> fadj[N];
	for (ll i=x;i<y;i++) {
		if ((i-x)%2) {
			fadj[a[i]].push_back(a[i+1]);
		} else {
			fadj[a[i+1]].push_back(a[i]);
		}
	}
	for (ll t=0;t<N;t++) {
		if (tfound[t]!=-1) {
			continue;
		}
		stack<ll> s;
		s.push(t);
		while (!s.empty()) {
			ll x = s.top(); s.pop();
			if (tfound[x]==t) {
				return 0;
			}
			if (tfound[x]>=0) {
				continue;
			}
			tfound[x]=t;
			for (ll y: fadj[x]) {
				s.push(y);
			}
		}
	}
	return 1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll K,Q; cin >> N >> K >> Q;
	for (ll i=0;i<N;i++) {
		cin >> a[i]; a[i]--;
	}
	ll j=N-1;
	for (ll i=(N-1);i>=0;i--) {
		while (j>0) {
			if (qry(j-1,i)) {
				j--;
			} else {
				break;
			}
		}
		ans[i]=j;
	}
	for (ll q=0;q<Q;q++) {
		ll x,y; cin >> x >> y;
		x--; y--;
		if (x>=ans[y]) {
			cout << "YES\n";
		} else {
			cout << "NO\n";
		}
	}
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8