Submission #852410

#TimeUsernameProblemLanguageResultExecution timeMemory
852410noyancanturkOsumnjičeni (COCI21_osumnjiceni)C++17
110 / 110
270 ms53084 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif #include <bits/stdc++.h> #define int long long #define pb push_back #define lim 1000000 using namespace std; const int mod=1000000007ll; multiset<pair<int,int>>cur; bool checky(pair<int,int>b){ if(!cur.size())return 1; auto it=cur.lower_bound({b.first,0}); if(it!=cur.end()){ //cerr<<"bruh\n"; if(it->first<=b.second)return 0; } if(it==cur.begin()){ //cerr<<"bruh1\n"; return 1; } it--; if(b.first<=it->second){ //cerr<<"bruh2\n"; return 0; } return 1; } void solve(){ int n; cin>>n; pair<int,int>a[n]; for(int i=0;i<n;i++){ cin>>a[i].first>>a[i].second; } int dp[n][20]; int j=0; for(int i=0;i<n;i++){ while(j<n&&checky(a[j])){ cur.insert(a[j]); j++; }// cerr<<(j<n)<<" "<<checky(a[j])<<"\n"; dp[i][0]=j-1; cur.erase(a[i]); } /* for(int i=0;i<n;i++)cerr<<dp[i][0]<<" "; cerr<<"\n"; */ for(int i=1;i<20;i++){ for(int j=0;j<n;j++){ if(dp[j][i-1]!=-1&&dp[j][i-1]+1<n)dp[j][i]=dp[dp[j][i-1]+1][i-1]; else dp[j][i]=-1; //cerr<<dp[j][i]<<" "; }//cerr<<"\n"; } int q; cin>>q; while(q--){ int x,y; cin>>x>>y; x--,y--; int res=0; for(int i=19;0<=i;i--){ if(y<x)break; if(dp[x][i]!=-1&&dp[x][i]<=y){ res+=1<<i; //cerr<<x<<" "<<i<<"\n"; x=dp[x][i]+1; }//else cerr<<"failed "<<x<<" "<<i<<"\n"; } if(x<=y)res++; cout<<res<<"\n"; //cerr<<"sure for now\n"; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #ifdef Local freopen("in","r",stdin); freopen("out","w",stdout); #endif int t=1; //cin>>t; while (t--) { solve(); } }
#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...