This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//éªè±é£é£å風å¯å¯
//天å°ä¸çè¼è«
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
int arr[500005];
int t[500005];
ii pos[500005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>n;
rep(x,0,n) cin>>t[x];
rep(x,0,n) cin>>arr[x];
rep(x,0,n){
pos[x]=ii(arr[x]-t[x],arr[x]+t[x]);
//cout<<pos[x].fi<<" "<<pos[x].se<<endl;
}
sort(pos,pos+n,[](ii i,ii j){
if (i.fi!=j.fi) return i.fi<j.fi;
else return i.se>j.se;
});
vector<int> v;
rep(x,0,n){
int it=pos[x].se;
if (v.empty() || v.back()<it) v.push_back(it);
else v[lower_bound(all(v),it)-v.begin()]=it;
}
cout<<sz(v)<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |