제출 #431580

#제출 시각아이디문제언어결과실행 시간메모리
431580errorgornLong Mansion (JOI17_long_mansion)C++17
10 / 100
3044 ms28868 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ii pair<ll,ll> #define fi first #define se second #define endl '\n' #define puf push_front #define pof pop_front #define pub push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--) #define all(x) (x).begin(),(x).end() #define sz(x) (int) (x).size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,q; int arr[500005]; vector<int> keys[500005]; ii queries[500005]; bool ans[500005]; int lpos[500005]; int rpos[500005]; int has[500005]; int bad[500005]; int main(){ cin.tie(0); cout.tie(0); cin.sync_with_stdio(false); cin>>n; rep(x,1,n) cin>>arr[x]; int a,b; rep(x,1,n+1){ cin>>a; rep(y,0,a){ cin>>b; keys[x].pub(b); } } cin>>q; rep(x,0,q) cin>>queries[x].fi>>queries[x].se; rep(zzz,0,2){ //change to 2 later rep(x,0,500005) has[x]=1e9; rep(x,n,1){ for (auto &it:keys[x+1]) has[it]=x+1; lpos[x]=has[arr[x]]; } rep(x,0,500005) has[x]=-1e9; rep(x,1,n){ for (auto &it:keys[x]) has[it]=x; rpos[x+1]=has[arr[x]]; } //rep(x,1,n+1) cout<<lpos[x]<<" "; cout<<endl; //rep(x,1,n+1) cout<<rpos[x]<<" "; cout<<endl; memset(bad,-1,sizeof(bad)); rep(x,1,n){ rep(y,x+2,n+1){ if (lpos[x]>=y && x>=rpos[y]) bad[x]=y; } if (lpos[x]==1e9) bad[x]=1e9; } //rep(x,1,n+1) cout<<bad[x]<<" "; cout<<endl<<endl; rep(x,0,q) if (queries[x].se<queries[x].fi){ //cout<<"query: "<<x<<endl; bool can=true; rep(y,queries[x].se,queries[x].fi){ //cout<<y<<" "<<bad[y]<<endl; if (queries[x].fi<bad[y]) can=false; } ans[x]=can; } //flip shit now reverse(arr+1,arr+n); reverse(keys+1,keys+n+1); rep(x,0,q) tie(queries[x].fi,queries[x].se)=ii(n-queries[x].fi+1,n-queries[x].se+1); } rep(x,0,q){ if (ans[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...