제출 #1160444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160444		_rain_	Arcade (NOI20_arcade)	C++17	0 / 100	0 ms	320 KiB

Arcade

#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;
	
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15