Submission #41525

#TimeUsernameProblemLanguageResultExecution timeMemory
41525grumpy_gordonLong Mansion (JOI17_long_mansion)C++14
100 / 100
491 ms262144 KiB
/* .:*+=%@@@@@@=-. .:=@#@@@#@@#######%==*. .-=####@######%*-.....:%##%. .*@###########%+:--........-%@- .*@##############@+--.........-:%- .+##################@==%%%%=+*:----+. .-@####################%++%@@@@@=+**%@@* .%###################@%%@@@###@%+:--%@@%. -@###################@%%%%*::*%++:-----=@+. -#####################@%=++++++*:-------.-=: .+####################@%++*::-:::--::*:::***=: .@#####################%=++*::::-:::++*=##@@#@- ..#####################@%%=++**:::::**+%@#@%%##-.. .%####################@@%=+++*+****::*=@######@. .=######################@%%==+==++**+=@%@##@###+:... -#######################@@@%%%===++=@@@%=++===*::--... -########################@@@@@@@%==%%=++==@@:::::*:--. ..:#########################@@@@@@%%======++++::-..:-.--... %#############################@###@%%@@%==%=%*----.--.::---. #############################################*-:*:-:---*---- . #############################################*--*--:---*---:-. #############################################+--::--::-*::-::. ###########################################+:*-.---.---.:---*-.. ###########################################**:-----------------. ##########################################@::**:--::::::--:::::- ###########################################:--:*:::::::::**::*+* ###########################################=:::***::::::**:::*+* ############################@@@@@@#########@+****::::********+++ ############################@%%%%%@@@@@@@###%+***::::::::***+==+ ############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+ #############################@%%%%%%%%%%@#####=::--------:*=%@%+ %###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%= ---------------------------------------------- -------------------------------------------- ---------------------------------------------- -------------------------------------------- ---------------------------------------------- o###########oo o##" ""##o o#" "## o#" "#o #" ## ## "## #" ## # ################### # # # # # # # # # # # # # #o # "#o ## "#o ## "#o o#" "#o ## "#o o#" "#ooo ooo#######oo ############### "######o o###"" "###o # ### o###o oooo ### oo####" o###**# #**# ############" ""##""""""""""########### # # oooooooo#"#** ## # # # # # ** ## # #o# #o# *****###ooo# ## ## o###o ## o##***## o########## #***#**##o o##" ""### #***##***# o#######o ### oo#### ##**####*# o##" ""#############"" ##****### ##" ## ##*##*### ## ### ##### ## ## ### # ## # ## ## # ## ## ## ### ## ###oo ### ""### ### ### */ #include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") //#pragma GCC target("avx,tune=native") //float __attribute__((aligned(32))) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; int mysqrt(ll x){ int l = 0, r = 1e9 + 1; while (r - l > 1){ int m = (l + r) / 2; if (m * (ll)m <= x) l = m; else r = m; } return l; } mt19937 rnd(1337); ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993; ll myrand(){ ll ZR = (XR * AR + YR * BR + CR) % MODR; XR = YR; YR = ZR; return ZR; } const int Mod = 1e9 + 7; int bpow(int x, int y){ if (y == 0) return 1; if (y == 1) return x; int ret = bpow(x, y >> 1); ret = (ret * (ll)ret) % Mod; if (y & 1) ret = (ret * (ll)x) % Mod; return ret; } int bdiv(int x, int y){ return (x * (ll)bpow(y, Mod - 2)) % Mod; } void setmin(int &x, int y){ x = min(x, y); } void setmax(int &x, int y){ x = max(x, y); } void setmin(ll &x, ll y){ x = min(x, y); } void setmax(ll &x, ll y){ x = max(x, y); } int gcd(int a, int b){ return a ? gcd(b % a, a) : b; } const ll llinf = 2e18 + 100; const double eps = 1e-9; const int maxn = 5e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17; int n; int arr[maxn]; vector<int> mas[maxn]; pair<int, int> ans[maxn]; pair<int, int> cl[maxn]; vector<int> moves[maxn]; void solve(){ for (int i = 0; i < n - 1; i++){ int l, r; int val = arr[i]; l = -1, r = mas[val].size(); while (r - l > 1){ int m = (l + r) / 2; if (mas[val][m] <= i) l = m; else r = m; } cl[i + 1].first = (l == -1 ? -1 : mas[val][l]); l++; cl[i + 1].second = (l < mas[val].size() ? mas[val][l] : n); } cl[n] = make_pair(-1, n); cl[0] = make_pair(-1, n); vector<int> g; for (int i = n - 1; i >= 0; i--){ while (!g.empty() && cl[g.back()].first >= cl[i + 1].first) moves[i].push_back(g.back()), g.pop_back(); g.push_back(i + 1); moves[i].push_back(-1); reverse(moves[i].begin(), moves[i].end()); } vector<int> q; for (int i = 0; i < n; i++){ while (!q.empty() && cl[q.back()].second <= cl[i].second) q.pop_back(); q.push_back(i); while (!q.empty()){ int l = -1, r = g.size(); while (r - l > 1){ int m = (l + r) / 2; if (cl[g[m]].first < q.back()) l = m; else r = m; } if (l >= 0 && g[l] <= cl[q.back()].second){ ans[i] = make_pair(q.back(), g[l] - 1); break; } else q.pop_back(); } for (auto x : moves[i]) if (x == -1) g.pop_back(); else g.push_back(x); } } int main() { #ifdef ONPC //ifstream cin("a.in"); //ofstream cout("a.out"); freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #else //ifstream cin("sprinklers.in"); //ofstream cout("sprinklers.out"); //freopen("road.in", "r", stdin); //freopen("road.out", "w", stdout); #endif // ONPC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n - 1; i++) cin >> arr[i], arr[i]--; for (int i = 0; i < n; i++){ int k; cin >> k; while (k--){ int x; cin >> x; mas[x - 1].push_back(i); } } solve(); //for (int i = 0; i < n; i++) //cout << ans[i].first << ' ' << ans[i].second << '\n'; int zap; cin >> zap; while (zap--){ int from, to; cin >> from >> to; from--; to--; if (ans[from].first <= to && to <= ans[from].second) cout << "YES\n"; else cout << "NO\n"; } }

Compilation message (stderr)

long_mansion.cpp: In function 'void solve()':
long_mansion.cpp:195:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         cl[i + 1].second = (l < mas[val].size() ? mas[val][l] : 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...