Submission #1339714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339714		ezzzay	Restore Array (RMI19_restore)	C++20	0 / 100	1094 ms	956 KiB

restore

#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];
    }
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            int u=0;
            vector<int>deg(n+10);
            unordered_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;
            }
            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