Submission #874874

#TimeUsernameProblemLanguageResultExecution timeMemory
874874tsumondaiOsumnjičeni (COCI21_osumnjiceni)C++14
110 / 110
242 ms50256 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 2e5 + 5, LOG=18; const int oo = 1e18, mod = 1e9 + 7; int n, m, k, q, lef[N], rig[N], par[N][LOG]; set<ii> st; vector<int> arr; bool can_insert(int ind) { if (st.empty()) return 1; auto it=st.lower_bound({lef[ind], 0}); int nxt=it->second; if (lef[ind]<=lef[nxt] && lef[nxt]<=rig[ind]) return 0; if (it!=st.begin()) { it--; int prv=it->second; if (lef[prv]<=lef[ind] && lef[ind]<=rig[prv]) return 0; } return 1; } void precalc() { int lim=0; foru(i,1,n) { if (lim<i) { st.clear(); lim=i; st.insert({lef[i], i}); } while (lim+1<=n && can_insert(lim+1)) { lim++; st.insert({lef[lim], lim}); } par[i][0]=lim+1; st.erase({lef[i], i}); } par[n+1][0]=n+1; foru(i,1,LOG-1) { foru(j,1,n+1) { par[j][i]=par[par[j][i-1]][i-1]; } } } int query(int a, int b) { int res=0; ford(i, LOG-1, 0) { if (par[a][i]<=b) { a=par[a][i]; res+=1<<i; } } return res+1; } void process() { cin >> n; foru(i,1,n) { cin >> lef[i] >> rig[i]; } precalc(); cin >> q; foru(i,1,q) { int a, b; cin >> a >> b; cout << query(a,b) << '\n'; } return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } /* Xét các trường hợp đặc biệt Kiểm tra lại input/output Cố gắng trâu Lật ngược bài toán Calm down and get VOI Flow: */
#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...