oj.uz

Submission #370609

# Submission time Handle Problem Language Result Execution time Memory
370609 2021-02-24T09:14:18 Z balbit Long Mansion (JOI17_long_mansion) C++14
0 / 100
 27 ms 24300 KB 
#include <bits/stdc++.h>
// #define BALBIT 1
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define SZ(x) (int)((x).size())
#define REP1(i,n) for(int i = 1; i<=n;++i)
#define REP(i,n)  for (int i = 0; i<n;++i)

#ifdef BALBIT
#define bug(...) cout<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cout<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&& ...y) {cout<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int inf = 1e9;
const int N = 500005;

int tol[21][N], tor[21][N], need[N], lb[N], rb[N];
int last[N];
vector<int> keys[N];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    // cout<<"HI";
    // bug("HI"); return 0;
    int n; cin>>n;
    assert(n<=10);
//    tol[0] = -inf;
    fill(last, last+n+1, -inf);
    REP1(i,n-1) cin>>need[i];
    REP1(i,n) {
        int k; cin>>k;
        REP(j,k) {
            int y; cin>>y; keys[i].pb(y);
            last[y] = i;
        }
        if(i !=n)
            tol[0][i] = last[need[i]];
        else
            tol[0][i] = -inf;
    }
    // return 0;
//    tol[n] = inf;
    fill(last, last+n+1, inf);
    for(int i = n; i>=1; --i) {
        for(int y : keys[i]) last[y] = i;
        if (i!=1)
            tor[0][i] = last[need[i-1]];
        else
            tor[0][i] = inf;
    }
    // return 0;
    REP1(j,20) {
        int df = (1<<(j-1));
        REP1(i,n) {
            tol[j][i] = tol[j-1][i];
            tor[j][i] = tor[j-1][i];
            if(i+df<=n)
                tol[j][i] = min(tol[j][i], tol[j-1][i+df]);
            if(i-df>=1)
                tor[j][i] = max(tor[j][i], tor[j-1][i-df]);
        }
    }
    // return 0;
    REP1(i,n) {
        // bug(i);
        if(rb[i-1] >= i) {
            // covered
            int at = i;
            for(int j = 20; j>=0; --j) {
                if(tol[j][at] >= i) {
                    at += (1<<j);
                    
                }
            }
            bug(at);
            if(tor[0][i]<=at) {
                lb[i] = lb[i-1]; rb[i] = rb[i-1];
            }else{
                lb[i] = i; rb[i] = at;
            }
        }else{
            lb[i] = rb[i] = i;
            for(;; ) {
                // grow to the left
                for(int j = 20; j>=0; --j) {
                    if(tor[j][lb[i]] <= rb[i]) {
                        lb[i] -= (1<<j);
                    }
                }
                if(tol[0][rb[i]] >= lb[i]) {
                    ++rb[i];
                }else break;
            }
                bug(i, lb[i], rb[i]);
        }
    }
    // return 0;
    int q; cin>>q;
    while(q--) {
        int x, y; cin>>x>>y;
        if(y>=lb[x]&&y<=rb[x]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 24300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 24300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 24300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 24300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -