Submission #1306739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306739		muhammad-ahmad	Alternating Heights (CCO22_day1problem1)	C++20	17 / 25	1096 ms	4560 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 3e3 + 5;

vector<int> adj[N];
int vis[N];

bool dfs(int u){
	vis[u] = 1;
	for (auto v : adj[u]){
		if (vis[v] == 1) return 0;
		if (vis[v] == 0 && !dfs(v)) return 0;
	}
	vis[u] = 2;
	return 1;
}

void solve() {
	int n, k, q; cin >> n >> k >> q;
	int a[N] = {}, B[N] = {};
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++){
		int l = i, r = n + 1;
		while (r - l > 1){
			bool c = 1;
			int mid = (l + r) / 2;
			for (int j = i; j <= mid; j++){
				vis[a[j]] = 0;
				adj[a[j]].clear();
			}
			for (int j = i; j < mid; j++){
				if (a[j] == a[j + 1]) c = 0;
				if ((j - i) % 2 == 0)
				adj[a[j]].push_back(a[j + 1]);
				else
				adj[a[j + 1]].push_back(a[j]);
			}
			for (int j = i; j <= mid; j++){
				if (vis[a[j]] == 0){
					c &= dfs(a[j]);
				}
			}
			if (c) l = mid;
			else r = mid;
		}
		B[i] = l;
	}
	for (int i = 1; i <= q; i++){
		int l, r; cin >> l >> r;
		if (B[l] >= r) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

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