Submission #652547

#TimeUsernameProblemLanguageResultExecution timeMemory
652547kymLong Mansion (JOI17_long_mansion)C++14
100 / 100
2407 ms143100 KiB
#include <bits/stdc++.h> using namespace std; #define int ll #define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i) #define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #else #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) #define reach cerr << "LINE: " << __LINE__ << "\n"; typedef pair <ll, ll> pi; typedef tuple<ll,ll,ll> ti3; typedef tuple<ll,ll,ll,ll> ti4; ll rand(ll a, ll b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (ll)1e18 + 500; template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; } template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; } const int MAXN = 500005; int n; int C[MAXN]; vector<int> V[MAXN]; struct SparseTable { vector<vector<int> > ST; int N, K; SparseTable(int _N, vector<int> a): N(_N) { K = MSB(N); ST.resize(K); ST[0] = a; for (int k = 1; k < K; ++k) for (int i = 0; i+(1<<k) <= N; ++i) ST[k].push_back( min(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) ); //min } /* returns most significant bit of an integer */ inline int MSB(unsigned int x) { return 32-__builtin_clz(x); } /* Min of range (x, x + 2^k-1) and (y-2^k+1, y) */ int query(int x, int y) { --x;--y; int k = MSB(y-x+1) - 1; return min(ST[k][x], ST[k][y-(1<<k)+1]); } }; map<int,int> pre; int goright[MAXN]; int goleft[MAXN]; int L[MAXN]; int R[MAXN]; int32_t main() { IAMSPEED cin >> n; FOR(i,1,n-1) cin >> C[i]; FOR(i,1,n) { int b; cin >> b; while(b--) { int x; cin >> x; V[i].pb(x); } } //lfseg=new node(1,n); //rgseg=new node(1,n); FOR(i,1,n-1) { for(auto key:V[i]){ pre[key]=i; } goright[i+1]=pre[C[i]]; } pre.clear(); DEC(i,n,1) { for(auto key:V[i]) { pre[key]=i; } if(pre.find(C[i-1]) != pre.end())goleft[i-1]=pre[C[i-1]]; else goleft[i-1]=n+1; } dba(goright,1,n); dba(goleft,1,n); /* FOR(i,1,n) { rgset->update(i,-goright[i]); } */ vector<int> v; FOR(i,1,n) { v.pb(goright[i]); } SparseTable ST=SparseTable(n,v); FOR(i,1,n) { L[i]=R[i]=i; int newl=L[i],newr=R[i]; reach db2(L[i],R[i]); do { L[i]=newl;R[i]=newr; db2(L[i],R[i]); int lo=R[i],hi=n+1; while(lo<hi-1) { int mid=(lo+hi)/2; if(ST.query(R[i]+1,mid) >= L[i])lo=mid; else hi=mid; } newr=lo; newl=L[i]; db(L[i]-1); if(L[i]!=1 && goleft[L[i]-1] <= R[i])newl=L[L[i]-1]; } while(newl!=L[i] || newr!=R[i]); } FOR(i,1,n) db2(L[i], R[i]); int q; cin >> q; while(q--) { int x,y; cin >> x >> y; if(L[x] <= y && y <= R[x])cout << "YES\n"; else cout << "NO\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...