Submission #1238401

#TimeUsernameProblemLanguageResultExecution timeMemory
1238401opeleklanosOsumnjičeni (COCI21_osumnjiceni)C++20
110 / 110
721 ms87960 KiB
#include <iostream> #include <vector> #include <set> using namespace std; #define ll long long vector<vector<ll>> lift; ll findLift(ll from, ll mn){ ll i = 0; ll par = 1; while(lift[from][i] <= mn) i++, par*=2; return par/2 + (i>0?findLift(lift[from][i-1], mn):0); } int main(void){ //freopen("input.txt", "r", stdin); vector<pair<ll, ll>> h; ll n; cin>>n; h.assign(n, {}); for(ll i = 0; i<n; i++) cin>>h[i].first>>h[i].second; vector<ll> step(n, 0); set<pair<ll, pair<ll, ll>>> s; ll nextSt = n; ll p2 = n; for(ll i = n-1; i>=0; i--){ auto e = s.lower_bound({h[i].first, {0, 0}}); while(e!=s.end() && e->first <= h[i].second){ p2--; s.erase({h[p2].first, {h[p2].second, p2}}); e = s.lower_bound({h[i].first, {0, 0}}); } while( e!= s.begin() && prev(e)->second.first >= h[i].first){ p2--; s.erase({h[p2].first, {h[p2].second, p2}}); e = s.lower_bound({h[i].first, {0, 0}}); } s.insert({h[i].first, {h[i].second, i}}); step[i] = p2; } lift.assign(n+1, vector<ll>(40, -1)); for(ll i = 0; i<40; i++) lift[n][i] = n; for(ll i = 0; i<n; i++) lift[i][0] = step[i]; for(ll i = n-1; i>=0; i--){ for(ll j = 1; j<40; j++){ lift[i][j] = lift[lift[i][j-1]][j-1]; } } ll q; cin>>q; for(ll i = 0; i<q; i++){ ll l, r; cin>>l>>r; cout<<findLift(l-1, r-1)+1<<endl; } 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...