Submission #625855

#	Time	Username	Problem	Language	Result	Execution time	Memory
625855		PurpleCrayon	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	764 ms	13864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;

bool has_cycle(vector<vector<int>>& adj) {
    int n = sz(adj);
    vector<int> deg(n);
    for (int a = 0; a < n; a++)
        for (int b : adj[a])
            deg[b]++;

    vector<int> q; q.reserve(n);
    for (int i = 0; i < n; i++) if (deg[i] == 0) q.push_back(i);
    for (int rep = 0; rep < sz(q); rep++) {
        int c = q[rep];
        for (auto nxt : adj[c]) {
            deg[nxt]--;
            if (deg[nxt] == 0)
                q.push_back(nxt);
        }
    }
    return sz(q) < n;
}
void solve() {
    int n, k, q; cin >> n >> k >> q;
    vector<int> a(n); for (auto& x : a) cin >> x, --x;

    vector<int> can(n);
    for (int rep : {0, 1}) {
        for (int l = rep, r = l; l < n; l += 2) {
            while (r < n) {
                vector<vector<int>> adj(k);
                for (int i = l; i < r; i++) {
                    if (i % 2 == l % 2) adj[a[i]].push_back(a[i + 1]);
                    else adj[a[i + 1]].push_back(a[i]);
                }
                if (has_cycle(adj)) break;
                r++;
            }
            can[l] = r;
        }
    }
    while (q--) {
        int l, r; cin >> l >> r, --l, --r;
        if (can[l] <= r) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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