Submission #370626

#TimeUsernameProblemLanguageResultExecution timeMemory
370626balbitLong Mansion (JOI17_long_mansion)C++14
100 / 100
1407 ms130796 KiB
#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; // int bigr = 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; } bug(i, lb[i], rb[i]); }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); } } int tmp = rb[i]; for(int j = 20; j>=0; --j) { if(tol[j][rb[i]] >= lb[i]) { rb[i] += (1<<j); } } if(tmp == rb[i]) break; } bug(i, lb[i], rb[i]); } } // return 0; int q; cin>>q; while(q--) { int x, y; cin>>x>>y; // bug(x,lb[x],rb[x],y); if(y>=lb[x]&&y<=rb[x]) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...