제출 #1160457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160457		_rain_	Arcade (NOI20_arcade)	C++17	100 / 100	204 ms	9800 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_y!=other.rorate_y) return rorate_y<other.rorate_y;
		return rorate_x<other.rorate_x;
	}
}; 
Point p[N+2];
class Solution{
	private:
		multiset<int>bag;
	public:
		void solve(){
			bag.clear();
			int cnt=0;
			for(int i=1;i<=m;++i){
				if (bag.size()){
					auto it=bag.lower_bound(p[i].rorate_x+1);
					--it;
					if (it!=bag.end() && *it<=p[i].rorate_x) bag.erase(it);
				}
				bag.insert(p[i].rorate_x);
			}
			cout<<bag.size();
		}
};
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].t;
	for(int i=1;i<=m;++i) cin>>p[i].a,p[i].rorate();
	sort(p+1,p+m+1);
	check_tool.solve();
}

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