oj.uz

Submission #431551

# Submission time Handle Problem Language Result Execution time Memory
431551 2021-06-17T12:55:59 Z lyc Long Mansion (JOI17_long_mansion) C++14
0 / 100
 3000 ms 117844 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<ll,ll> pll;

const int mxN = 5e5+5;

int N, C[mxN], Q;
set<int> keys[mxN], kright[mxN], k3[mxN];
int goleft[mxN], goright[mxN];

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    FOR(i,1,N-1){
        cin >> C[i];
    }
    C[0] = C[N] = 1e9+5; // impossible
    FOR(i,1,N){
        int B; cin >> B;
        FOR(j,1,B){
            int A; cin >> A;
            keys[i].insert(A);
        }
    }

    RFOR(i,N,1){
        goright[i] = i;
        for (auto& x : keys[i]) kright[i].insert(x);
        while (keys[i].count(C[goright[i]])) {
            mergeto(kright[goright[i]+1], kright[i]);
            goright[i] = goright[goright[i]+1];
        }
        //cout << i << ": "; for (auto& x : kright[i]){ cout << x << ' '; } cout << endl;
        goleft[i] = kright[i].count(C[i-1]) ? i-1 : i;
    }

    k3[1] = kright[1];
    FOR(i,1,N){
        for (auto& x : keys[i]) k3[i].insert(x);
        if (goleft[i] < i) {
            goleft[i] = goleft[goleft[i]];
            goright[i] = max(goright[i], goright[goleft[i]]);
            mergeto(k3[goleft[i]], k3[i]);
            FOR(j,goright[goleft[i]]+1,goright[i]) for (int x : keys[j]) k3[i].insert(x);
            //TRACE(goleft[i] _ C[goleft[i]-1]);
            //cout << i << ": "; for (auto& x : kright[i]){ cout << x << ' '; } cout << endl;
            while (true) {
                if (k3[i].count(C[goleft[i]-1])) {
                    mergeto(k3[goleft[i]-1], k3[i]);
                    goleft[i] = goleft[goleft[i]-1];
                    goright[i] = max(goright[i], goright[goleft[i]]);
                } else if (k3[i].count(C[goright[i]])) {
                    ++goright[i];
                    for (auto& x : keys[goright[i]]) k3[i].insert(x);
                } else break;
            }
        }
        //TRACE( i _ goleft[i] _ goright[i] );
    }

    cin >> Q;
    FOR(i,1,Q){
        int X, Y; cin >> X >> Y;
        cout << (goleft[X] <= Y && Y <= goright[X] ? "YES" : "NO") << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 71540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 71540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 117844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 71540 KB Output isn't correct
2 Halted 0 ms 0 KB -