| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 915425 | yutabi | Osumnjičeni (COCI21_osumnjiceni) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r || (ql <= l && r <= qr)){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}#define pb push_back#define mp make_pairusing namespace std; const int mod = 998244353; struct SEGT{ vector<int> tree, lazy; void init(int n){ tree.assign(4*n, 0); lazy.assign(4*n, 0); } void push(int ind){ tree[ind*2] += lazy[ind]; tree[ind*2+1] += lazy[ind]; lazy[ind*2] += lazy[ind]; lazy[ind*2+1] += lazy[ind]; lazy[ind] = 0; } void update(int ind, int l, int r, int ql, int qr, int val){ if(l > r || l > qr || r < ql) return; if(l == r){ tree[ind] += val; lazy[ind] += val; } else{ push(ind); int m = (l + r)/2; update(ind*2, l, m, ql, qr, val); update(ind*2+1, m+1, r, ql, qr, val); tree[ind] = max(tree[ind*2], tree[ind*2+1]); } } int query(int ind, int l, int r, int ql, int qr){ if(l > r || l > qr || r < ql) return 0; if(l >= ql && r <= qr) return tree[ind]; else{ push(ind); int m = (l + r)/2; return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr)); } }}; int main(){ int n; cin>>n; vector<pair<int, int> > a(n); set<int> ste; for(int i = 0; i < n; i++){ int l, r; cin>>l>>r; ste.insert(l); ste.insert(r); a[i] = mp(l, r); } map<int, int> conv; int val = 1; for(auto itr: ste){ conv[itr] = val; val++; } for(int i = 0; i < n; i++){ a[i] = mp(conv[a[i].first], conv[a[i].second]); } int N = val + 5; SEGT seg; seg.init(N); vector<int> go(n); int r = 0; for(int l = 0; l < n; l++){ while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){ seg.update(1, 1, N, a[r].first, a[r].second, 1); r++; } go[l] = r; seg.update(1, 1, N, a[l].first, a[l].second, -1); } int K = 18; vector<vector<int> > lift(K, vector<int>(n+1)); for(int i = 0; i < n; i++){ lift[0][i] = go[i]; } lift[0][n] = n; for(int i = 1; i < K; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; int ans = 1; l--, r--; for(int i = K-1; i >= 0; i--){ if(lift[i][l] <= r){ l = lift[i][l]; ans += (1 << i); } } cout<<ans<<endl; } return 0;}