Submission #1339715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339715		ezzzay	Restore Array (RMI19_restore)	C++20	0 / 100	1096 ms	852 KiB

restore

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
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];
    }
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            int u=0;
            vector<int>deg(n+10);
            vector<bool>vis(n+10);
            for(int i=l;i<=r;i++){
                vc[a[i]].clear();
                vis[a[i]]=1;
            }
            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(int i=1;i<=n;i++){
                if(vis[i]){
                     if(deg[i]==0){
                    q.push(i);
                 }
                }
            }
            while(!q.empty()){
                auto x=q.front();
                q.pop();
                vis[x]=0;
                for(auto y:vc[x]){
                    deg[y]--;
                    if(deg[y]==0){
                        q.push(y);
                    }
                }
            }
            int h=0;
            for(int i=1;i<=n;i++){
                h+=vis[i];
            }
            if(h==0){
                ans[l][r]=1;
            }
            else{
                ans[l][r]=2;
            }
        
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(ans[l][r]==1){
            cout<<"YES"<<endl;
            continue;
        }
        else {
            cout<<"NO"<<endl;
            continue;
        }
        
        
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55