Submission #204514

#	Time	Username	Problem	Language	Result	Execution time	Memory
204514		balbit	Long Mansion (JOI17_long_mansion)	C++14	0 / 100	3079 ms	38412 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define SZ(x) x.size()
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<#__VA_ARGS__<<" : ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#endif // BALBIT

const int mod = 1e9+7;

const int maxn = 5e5+3;

struct que{
    int pos, id;
};
int ans[maxn], ed[maxn], far[maxn]; // ed is color of the one to the left, far is the farthest right it can go
//set<int> key[maxn], rset[maxn]; // set of the things that go to its right
vector<int> keyat[maxn]; // Where the keys are for this color
bool have[maxn]; // keys i have
vector<que> QQ[maxn];

bool is(int x, int l, int r) { // is there x between l and r (inclusive)?
    return upper_bound(ALL(keyat[x]),r) != lower_bound(ALL(keyat[x]),l);
}

void merg(set<int> &a, set<int> &b) {
    if (SZ(a)<SZ(b)) a.swap(b);
    for (int x : b) a.insert(x);
    b.clear();
}

pii rch[maxn];

signed main(){
    IOS();
    int n,q; cin>>n;
    for (int i = 1; i<n; i++) {
        cin>>ed[i];
    }
    for (int i = 0; i<n; i++){
        int m; cin>>m;
        for (int j = 0;j<m; j++){
            int x; cin>>x; // Colors are 1-based
//            key[i].insert(x);
//            rset[i].insert(x);
            keyat[x].pb(i);
        }
    }
//    for (int i = n-1; i>=0 ; i--) {
//        far[i] = i;
//        while (far[i] < n-1 && rset[i].count(ed[far[i]+1])) {
//            merg(rset[i],rset[far[i]+1]);
//            far[i] = far[far[i]+1];
//        }
//        bug(i,far[i]);
//        for (int x : rset[i]) {
//            bug(x);
//        }
//    }
    cin>>q;
    for (int i = 0; i<q; i++) {
        int fr, to;
        cin>>fr>>to; --fr; --to;
        QQ[fr].pb({to,i});
    }
    for (int i = 0; i<n; i++) rch[i] = {i,i};
    for (int i = 0; i<n; i++) {
        bool B = 1;
        int L = rch[i].f, R = rch[i].s;
        while (B) {
            B=0;
            if (is(ed[L], L, R)) {
                // can reach L-1
                L = min (L, rch[L-1].f);
                R = max (R, rch[L-1].s);
                B = 1;
            }
            if (is (ed[R+1], L, R)){
                // can reach R+1
                L = min(L,rch[R+1].f);
                R = max(R,rch[R+1].s);
                B = 1;
            }
        }
        for (que ele : QQ[i]) {
            if (ele.pos>=L && ele.pos<=R) {
                ans[ele.id] = 1;
            }
        }
        rch[i] = {L,R};
    }
    for (int i = 0; i<q; i++) {
        if (ans[i]) {
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75