# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1160443 | _rain_ | Arcade (NOI20_arcade) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int N=(int)5e5;
int n,m;
struct Point{
int t,a;
int rorate_x,rorate_y;
void rorate(){
rorate_x=t-a;
rorate_y=t+a;
}
bool operator < (const Point&other) const{
if (rorate_x!=other.rorate_x) return rorate_x<other.rorate_x;
return rorate_y<other.rorate_y;
}
};
Point p[N+2];
class Solution{
private:
public:
multiset<int>bag;
bool check(int x){
bag.clear();
int cnt=0;
for(int i=1;i<=m;++i){
// cout<<p[i].rorate_x<<' '<<p[i].rorate_y<<'\n';
if (bag.size()){
auto it=bag.lower_bound(p[i].rorate_y+1);
--it;
if (it!=bag.end() && *it<=p[i].rorate_y) {
int x_x=*it;
bag.erase(it);
}
}
bag.insert(p[i].rorate_y);
if (bag.size()>x) return false;
}
return true;
}
};
Solution check_tool;
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("txt.inp","r",stdin);
// freopen("txt.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;++i) cin>>p[i].a;
for(int i=1;i<=m;++i) cin>>p[i].t,p[i].rorate();
sort(p+1,p+m+1);
int low=0,high=m,ans=-1;
while (low<=high){
int mid=(low+high)/2;
if (check_tool.check(mid)){
ans=mid;
high=mid-1;
}
else low=mid+1;
}
cout<<ans;
}