Submission #957601

#TimeUsernameProblemLanguageResultExecution timeMemory
957601parlimoosLong Mansion (JOI17_long_mansion)C++14
25 / 100
2432 ms50548 KiB
//Be Name KHODA #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pp pop_back #define lb lower_bound #define ub upper_bound #define cl clear #define bg begin #define arr(x) array<int , x> #define endl '\n' int n , q , in[500000][2]; vector<int> inxs[500000]; int seg[2000001][2] , seginf[2000001][2]; void init(){ for(int i = 0 ; i < n ; i++){ if(in[i][0] != -1){ auto itr = lb(inxs[in[i][0]].bg() , inxs[in[i][0]].end() , i); if(itr == inxs[in[i][0]].bg()) in[i][0] = -1; else in[i][0] = *(--itr); } if(in[i][1] != -1){ auto itr = ub(inxs[in[i][1]].bg() , inxs[in[i][1]].end() , i); if(itr == inxs[in[i][1]].end()) in[i][1] = n; else in[i][1] = *(itr); } } } void buildSeg(int l = 0 , int r = n - 1 , int i = 1){ seginf[i][0] = l , seginf[i][1] = r; if(l == r){ seg[i][0] = in[l][0]; seg[i][1] = in[l][1]; }else{ int c = (r + l - 1) >> 1; buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1); seg[i][0] = min(seg[i << 1][0] , seg[(i << 1) | 1][0]); seg[i][1] = max(seg[i << 1][1] , seg[(i << 1) | 1][1]); } } int getSeg(int l , int r , int i , int md){ if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i][md]; if(seginf[i][1] >= l and seginf[i][0] <= r){ if(md == 0) return min(getSeg(l , r , i << 1 , md) , getSeg(l , r , (i << 1) | 1 , md)); return max(getSeg(l , r , i << 1 , md) , getSeg(l , r , (i << 1) | 1 , md)); } if(md == 0) return n; return -1; } int bsmx(int l , int r){ int i = l , j = r; l--; while(r - l - 1 > 1){ int c = (r + l + 1) >> 1; if(getSeg(i , c , 1 , 1) >= j) r = c; else l = c - 1; } if(r - l - 1 == 1 and getSeg(i , r - 1 , 1 , 1) >= j) return r - 1; return r; } int bsmn(int l , int r){ int i = l , j = r; r++; while(r - l - 1 > 1){ int c = (r + l + 1) >> 1; if(getSeg(c , j , 1 , 0) <= i) l = c - 1; else r = c; } if(r - l - 1 == 1 and getSeg(l + 1 , j , 1 , 0) <= i) return l + 1; return l; } void f(){ buildSeg(); for(int i = 0 ; i < n ; i++){ if(in[i][0] != -1){ in[i][0] = bsmx(in[i][0] , i); } if(in[i][1] != n){ in[i][1] = bsmn(i , in[i][1]); } } buildSeg(); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; in[0][0] = -1 , in[n - 1][1] = n; for(int i = 1 ; i < n ; i++){ int d; cin >> d; in[i - 1][1] = d - 1 , in[i][0] = d - 1; } for(int i = 0 ; i < n ; i++){ int b; cin >> b; for(int j = 0 ; j < b ; j++){ int d; cin >> d; inxs[d - 1].pb(i); } } init() , f(); cin >> q; for(int i = 0 ; i < q ; i++){ int v , u; cin >> v >> u; v-- , u--; if(v < u){ int d = getSeg(v + 1 , u , 1 , 0); if(d >= v) cout << "YES\n"; else cout << "NO\n"; }else{ int d = getSeg(u , v - 1 , 1 , 1); if(d <= v) 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...