제출 #1239300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239300		altern23	Arcade (NOI20_arcade)	C++20	100 / 100	167 ms	29244 KiB

Arcade

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

/*

*/

• 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