제출 #1239300

#제출 시각아이디문제언어결과실행 시간메모리
1239300altern23Arcade (NOI20_arcade)C++20
100 / 100
167 ms29244 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const ld eps = 1e-6;

vector<ll> pos[MAXN + 5];
ll t[MAXN + 5], a[MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M; cin >> N >> M;
		for(int i = 1; i <= M; i++) cin >> t[i];
		for(int i = 1; i <= M; i++) cin >> a[i];
		vector<pii> intervals;
		for(int i = 1; i <= M; i++){
			intervals.push_back({a[i] - t[i], a[i] + t[i]});
		}
		sort(intervals.begin(), intervals.end(), [&](pii x, pii y){
			if(x.fi == y.fi) return x.sec > y.sec;
			return x.fi < y.fi;
		});
		
		set<ll> st;
		for(auto [l, r] : intervals){
			if(!st.size()){
				st.insert(r);
				continue;
			}
			auto x = st.lower_bound(r);
			if(x != st.end()) st.erase(x);
			st.insert(r);
		}
		
		cout << (ll)st.size() << "\n";
	}
}

/*

*/
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...