Submission #1024085

#TimeUsernameProblemLanguageResultExecution timeMemory
1024085Ghulam_JunaidOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
54 ms15956 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second const int N = 2e5 + 10, LG = 18; int n, q, par[N][LG]; pair<int, int> a[N]; set<pair<int, int>> st; bool check(int i){ if (st.find({a[i].first, a[i].second}) != st.end()) return 0; bool good = 1; st.insert({a[i].first, a[i].second}); auto p = st.find({a[i].first, a[i].second}); p++; if (p != st.end()){ auto P = *p; if (P.F > a[i].second) good = 1; else good = 0; } p--; if (p != st.begin()){ p--; auto P = *p; if (P.S < a[i].first) good = 1; else good = 0; } if (!good) st.erase({a[i].first, a[i].second}); return good; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second; par[n + 1][0] = n + 1; int r = 1; for (int i = 1; i <= n; i ++){ while (r <= n and check(r)) r++; par[i][0] = r; st.erase({a[i].first, a[i].second}); } for (int jump = 1; jump < LG; jump ++) for (int i = 1; i <= n + 1; i ++) par[i][jump] = par[par[i][jump - 1]][jump - 1]; cin >> q; while (q--){ int u, v; cin >> u >> v; int ans = 0; for (int j = LG - 1; j >= 0; j --){ if ((par[u][j]) <= v){ u = par[u][j]; ans += (1 << j); } } cout << ans + 1 << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...