제출 #862344

#제출 시각아이디문제언어결과실행 시간메모리
862344TAhmed33Osumnjičeni (COCI21_osumnjiceni)C++98
0 / 110
44 ms20828 KiB
#include <bits/stdc++.h> using namespace std; #define mid ((l + r) >> 1) bool intersect (pair <int, int> a, pair <int, int> b) { return !(a.second < b.first || b.second < a.first); } const int MAXN = 2e5 + 25; const int MAXL = 1e9 + 25; const int MAXN2 = 5e5 + 25; struct SegmentTree { int tree[MAXN2], lazy[MAXN2]; int tl[MAXN2], tr[MAXN2]; int cnt = 1; void init () { for (int i = 1; i < MAXN2; i++) { tl[i] = tr[i] = lazy[i] = -1; } } void ext (int node) { if (tl[node] == -1) tl[node] = ++cnt; if (tr[node] == -1) tr[node] = ++cnt; } void prop (int l, int r, int node) { if (lazy[node] == -1) return; if (l != r) { ext(node); lazy[tl[node]] = lazy[node]; lazy[tr[node]] = lazy[node]; } tree[node] = lazy[node]; lazy[node] = -1; } void update (int l, int r, int a, int b, int c, int node) { prop(l, r, node); if (l > b || r < a) return; if (l >= a && r <= b) { lazy[node] = c; prop(l, r, node); return; } update(l, mid, a, b, c, tl[node]); update(mid + 1, r, a, b, c, tr[node]); tree[node] = min(tree[tl[node]], tree[tr[node]]); } int get (int l, int r, int a, int b, int node) { prop(l, r, node); if (l > b || r < a) return 1e9; if (l >= a && r <= b) return tree[node]; return min(get(l, mid, a, b, tl[node]), get(mid + 1, r, a, b, tr[node])); } } cur; pair <int, int> arr[MAXN]; int nxt[MAXN]; int main () { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second; arr[n + 1].first = 1; arr[n + 1].second = 1e9; cur.init(); cur.update(1, MAXL, -MAXL, MAXL, n + 1, 1); for (int i = n; i >= 1; i--) { nxt[i] = cur.get(1, MAXL, arr[i].first, arr[i].second, 1); cur.update(1, MAXL, arr[i].first, arr[i].second, i, 1); } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; int dp[n + 1] = {}; for (int i = r; i >= l; i--) { if (nxt[i] > r) { dp[i] = 1; } else { dp[i] = 1 + dp[nxt[i]]; } } cout << dp[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...
#Verdict Execution timeMemoryGrader output
Fetching results...