Submission #966888

#	Time	Username	Problem	Language	Result	Execution time	Memory
966888		Jomnoi	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	743 ms	13940 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 3005;

int A[MAX_N], fur[MAX_N];
vector <int> graph[MAX_N];
int visited[MAX_N];

bool dfs(int u) {
    if (visited[u] == 2) return true;
    if (visited[u] == 1) return false;
    visited[u] = 1;

    for (auto v : graph[u]) {
        if (dfs(v) == false) return false;
    }
    visited[u] = 2;
    return true;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, K, Q;
    cin >> N >> K >> Q;

    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) {
        int l = i, r = N;
        while (l <= r) {
            int mid = (l + r) / 2;

            for (int j = 1; j <= K; j++) {
                visited[j] = 0;
                graph[j].clear();
            }
            for (int j = i + 1; j <= mid; j++) {
                if (j % 2 == 1) graph[A[j]].push_back(A[j - 1]);
                else graph[A[j - 1]].push_back(A[j]);
            }

            bool ok = true;
            for (int j = 1; j <= K; j++) {
                if (visited[j] == 0 and dfs(j) == false) ok = false;
            }

            if (ok == true) l = mid + 1, fur[i] = mid;
            else r = mid - 1;
        }
    }

    while (Q--) {
        int x, y;
        cin >> x >> y;

        if (fur[x] >= y) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

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