Submission #1339712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339712		ezzzay	Alternating Heights (CCO22_day1problem1)	C++20	7 / 25	1097 ms	47256 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=5002;
int a[N];
vector<int>vc[N];
int ans[N][N];
signed main(){
    int n,k,q;
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(ans[l][r]==1){
            cout<<"YES"<<endl;
            continue;
        }
        else if(ans[l][r]==2){
            cout<<"NO"<<endl;
            continue;
        }
        int u=0;
        vector<int>deg(n+10);
        set<int>st;
        for(int i=l;i<=r;i++){
            vc[a[i]].clear();
            st.insert(a[i]);
        }
        for(int i=l;i<r;i++){
            u^=1;
            if(u){
                vc[a[i]].pb(a[i+1]);
                deg[a[i+1]]++;
            }
            else{
                vc[a[i+1]].pb(a[i]);
                deg[a[i]]++;
            }
        }
        queue<int>q;
        for(auto x:st){
            if(deg[x]==0){
                q.push(x);
            }
        }
        while(!q.empty()){
            auto x=q.front();
            q.pop();
            st.erase(x);
            for(auto y:vc[x]){
                deg[y]--;
                if(deg[y]==0){
                    q.push(y);
                }
            }
        }
        if(st.empty()){
            ans[l][r]=1;
            cout<<"YES"<<endl;
        }
        else{
            ans[l][r]=2;
            cout<<"NO"<<endl;
        }
        
        
        
        
    }
}

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