Submission #1099656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099656		Math4Life2020	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	581 ms	14116 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 ncount = 0;
	ll tfound[N];
	ll fleft[N];
	for (ll i=0;i<N;i++) {
		tfound[i]=-1;
	}
	vector<ll> fadj[N];
	vector<ll> radj[N];
	for (ll i=x;i<y;i++) {
		if ((i-x)%2) {
			fadj[a[i]].push_back(a[i+1]);
			radj[a[i+1]].push_back(a[i]);
		} else {
			fadj[a[i+1]].push_back(a[i]);
			radj[a[i]].push_back(a[i+1]);
		}
	}
	stack<pii> s;
	for (ll i=0;i<N;i++) {
		fleft[i]=fadj[i].size();
		if (fadj[i].size()==0) {
			s.push({i,0});
		}
	}
	while (!s.empty()) {
		pii p0 = s.top(); s.pop();
		ncount++;
		ll x = p0.first; ll t = p0.second;
		if (tfound[x]!=-1) {
			return 0;
		}
		tfound[x]=t;
		for (ll y: radj[x]) {
			fleft[y]--;
			if (fleft[y]==0) {
				s.push({y,t+1});
			}
		}
	}
	if (ncount!=N) {
		return 0;
	}
	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: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8