Submission #114057

#TimeUsernameProblemLanguageResultExecution timeMemory
114057popovicirobertLong Mansion (JOI17_long_mansion)C++14
5 / 100
3041 ms13608 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; vector <char> lg; inline int get_mx(int x, int y, vector < vector <int> > &rmq, vector <int> &arr) { int bit = lg[y - x + 1]; return max(arr[rmq[x][bit]], arr[rmq[y - (1 << bit) + 1][bit]]); } inline int get_mn(int x, int y, vector < vector <int> > &rmq, vector <int> &arr) { int bit = lg[y - x + 1]; return min(arr[rmq[x][bit]], arr[rmq[y - (1 << bit) + 1][bit]]); } vector <bool> sol; int n, q; inline void solve(vector <int> &c, vector < vector <int> > &key, vector < pair <int, int> > &qry) { vector <int> last(n + 1, -1), prv(n + 1, -1), nxt(n + 1, -1); int i; for(i = 1; i < n; i++) { for(auto it : key[i]) { last[it] = i; } prv[i + 1] = last[c[i]]; } fill(last.begin(), last.end(), n + 1); for(i = n - 1; i >= 1; i--) { for(auto it : key[i + 1]) { last[it] = i + 1; } nxt[i] = last[c[i]]; } /*vector < vector <int> > rmq(n + 1, vector <int>(19)); for(i = 1; i <= n; i++) { rmq[i][0] = i; } for(int bit = 1; (1 << bit) <= n; bit++) { for(i = 1; i + (1 << bit) <= n + 1; i++) { int x = rmq[i][bit - 1], y = rmq[i + (1 << (bit - 1))][bit - 1]; if(nxt[x] > nxt[y]) { rmq[i][bit] = x; } else { rmq[i][bit] = y; } } } vector <int> len(n + 1); for(i = 1; i <= n; i++) { if(prv[i] == -1) { len[i] = -1; continue; } int res = prv[i]; for(int step = 1 << 18; step; step >>= 1) { if(res + step <= n && get_mx(prv[i], res + step, rmq, nxt) <= i) { res += step; } } len[i] = res + 1; } for(int bit = 1; (1 << bit) <= n; bit++) { for(i = 1; i + (1 << bit) <= n + 1; i++) { int x = rmq[i][bit - 1], y = rmq[i + (1 << (bit - 1))][bit - 1]; if(len[x] < len[y]) { rmq[i][bit] = x; } else { rmq[i][bit] = y; } } }*/ for(i = 1; i <= q; i++) { int x = qry[i].first, y = qry[i].second; if(x > y) { continue; } //sol[i] = (get_mn(x + 1, y, rmq, len) >= x); sol[i] = 1; for(int p = x + 1; p <= y && sol[i]; p++) { if(prv[p] == -1) { sol[i] = 0; break; } for(int j = prv[p]; j < x; j++) { if(nxt[j] >= p) { sol[i] = 0; break; } } } } } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; lg.resize(n + 1); for(i = 2; i <= n; i++) { lg[i] = lg[i >> 1] + 1; } vector <int> c(n); for(i = 1; i < n; i++) { cin >> c[i]; } vector < vector <int> > key(n + 1); for(i = 1; i <= n; i++) { int x; cin >> x; while(x > 0) { x--; int id; cin >> id; key[i].push_back(id); } } cin >> q; vector < pair <int, int> > qry(q + 1); for(i = 1; i <= q; i++) { int x, y; cin >> x >> y; qry[i] = {x, y}; } sol.resize(q + 1); solve(c, key, qry); for(i = 1; i <= q; i++) { qry[i].first = n - qry[i].first + 1; qry[i].second = n - qry[i].second + 1; } for(i = 1; i < n - i; i++) { swap(c[i], c[n - i]); } for(i = 1; i < n - i + 1; i++) { swap(key[i], key[n - i + 1]); } solve(c, key, qry); for(i = 1; i <= q; i++) { if(sol[i] == 0) { cout << "NO\n"; } else { cout << "YES\n"; } } //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...