oj.uz

Submission #1099654

# Submission time Handle Problem Language Result Execution time Memory
1099654 2024-10-12T00:43:52 Z Math4Life2020 Alternating Heights (CCO22_day1problem1) C++17
0 / 25
 348 ms 12880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 12880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 11096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 306 ms 608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 12880 KB Output isn't correct
2 Halted 0 ms 0 KB -