Submission #529971

#TimeUsernameProblemLanguageResultExecution timeMemory
529971chenyanExhibition (JOI19_ho_t2)C++17
100 / 100
311 ms6212 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define all(x) x.begin(),x.end() #define pb emplace_back #define N 100010 #define ff first #define ss second pii a[N]; int n,m,ans,c[N]; bool f(int x){ int i,j,mx=0; priority_queue<int,vector<int>,greater<int>>pq; for(i=m-x,j=0;i<m;i++){ while(j<n&&a[j].ff<=c[i]) pq.push(a[j++].ss); while(!pq.empty()&&pq.top()<mx) pq.pop(); if(pq.empty()) return 0; mx=pq.top(),pq.pop(); } return 1; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int i,j; cin>>n>>m; for(i=0;i<n;i++) cin>>a[i].ff>>a[i].ss; for(i=0;i<m;i++)cin>>c[i]; sort(c,c+m); sort(a,a+n); for(i=m,j=0;i;i>>=1){ while(i+j<=m&&f(i+j)) ans=max(ans,i+j),j+=i; } cout<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...