Submission #851648

#	Time	Username	Problem	Language	Result	Execution time	Memory
851648		khanhphucscratch	Alternating Heights (CCO22_day1problem1)	C++14	25 / 25	247 ms	9296 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector<int> ad[3001];
int k, f[3001], a[3001], val[3001], state[3001];
bool ok = 1, exist[3001];
void dfs(int u)
{
    state[u] = 1;
    for(int v : ad[u]) if(state[v] < 2){
        if(state[v] == 1){ok = 0; return;}
        else{
            dfs(v);
            if(ok == 0) return;
        }
    }
    state[u] = 2;
}
bool check(int l, int r)
{
    for(int i = 1; i <= k; i++){
        ad[i].clear();
        f[i] = 0; state[i] = 0; exist[i] = 0;
    }
    for(int i = l; i <= r; i++){
        exist[a[i]] = 1;
        if(i%2 == 1){
            if(i-1 >= l){
                ad[a[i]].push_back(a[i-1]);
                f[a[i-1]]++;
            }
            if(i+1 <= r){
                ad[a[i]].push_back(a[i+1]);
                f[a[i+1]]++;
            }
        }
    }
    ok = 1;
    for(int i = 1; i <= k; i++) if(f[i] == 0){
        dfs(i);
        if(ok == 0) return 0;
    }
    for(int i = 1; i <= k; i++) if(exist[i] == 1 && state[i] == 0) return 0;
    return ok;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin>>n>>k>>q;
    map<pair<int, int>, int> f;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int j = 1;
    for(int i = 1; i <= n; i++){
        while(j <= n && check(i, j) == 1) j++;
        val[i] = j;
    }
    for(int i = 1; i <= q; i++){
        int l, r;
        cin>>l>>r;
        if(val[l] <= r) cout<<"NO"<<'\n';
        else cout<<"YES"<<'\n';
    }
}

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