Submission #1202444

#TimeUsernameProblemLanguageResultExecution timeMemory
1202444zNatsumiOsumnjičeni (COCI21_osumnjiceni)C++20
110 / 110
837 ms27904 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; const int RANDOM = chrono::steady_clock::now().time_since_epoch().count(); struct chash{ bool operator()(int x){ return x ^ RANDOM; } }; const int N = 2e5 + 5; int n, q, l[N], r[N], m, jump[N][20]; void compress(){ vector<int> rrh; for(int i = 1; i <= n; i++){ rrh.push_back(l[i]); rrh.push_back(r[i]); } sort(rrh.begin(), rrh.end()); rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end()); for(int i = 1; i <= n; i++){ l[i] = lower_bound(rrh.begin(), rrh.end(), l[i]) - rrh.begin() + 1; r[i] = lower_bound(rrh.begin(), rrh.end(), r[i]) - rrh.begin() + 1; } m = rrh.size(); } namespace IT{ int st[N<<3], lz[N<<3]; void push(int i){ if(!lz[i]) return; st[i<<1] += lz[i]; st[i<<1|1] += lz[i]; lz[i<<1] += lz[i]; lz[i<<1|1] += lz[i]; lz[i] = 0; } void update(int l, int r, int x, int tl, int tr, int i){ if(r < tl || tr < l || l > r) return; if(l <= tl && tr <= r){ st[i] += x; lz[i] += x; return; } push(i); int tm = tl + tr >> 1; update(l, r, x, tl, tm, i<<1); update(l, r, x, tm + 1, tr, i<<1|1); st[i] = max(st[i<<1], st[i<<1|1]); } bool get(int l, int r, int tl, int tr, int i){ if(r < tl || tr < l || l > r) return 0; if(l <= tl && tr <= r) return st[i]; push(i); int tm = tl + tr >> 1; return max(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1)); } } int32_t main(){ cin.tie(0)->sync_with_stdio(0); // #define task "test" // if(fopen(task ".inp", "r")){ // freopen(task ".inp", "r", stdin); // freopen(task ".out", "w", stdout); // } cin >> n; for(int i = 1; i <= n; i++) cin >> l[i] >> r[i]; compress(); for(int i = 1, j = 0; i <= n; i++){ while(j < n && !IT::get(l[j + 1], r[j + 1], 1, m, 1)){ j += 1; IT::update(l[j], r[j], 1, 1, m, 1); } jump[i][0] = j + 1; IT::update(l[i], r[i], -1, 1, m, 1); } for(int i = 1; i <= n; i++) cerr << jump[i][0] << " \n"[i == n]; for(int j = 1; j <= 17; j++) for(int i = 1; i <= n; i++) if(jump[i][j - 1] <= n) jump[i][j] = jump[jump[i][j - 1]][j - 1]; cin >> q; while(q--){ int u, v; cin >> u >> v; int res = 0; for(int i = 17; i >= 0; i--) if(0 < jump[u][i] && jump[u][i] <= v){ res += (1 << i); u = jump[u][i]; } cout << res + (u <= v) << "\n"; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...