Submission #11379110


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

template<typename T>
int LIS(const vector<T> &a){
    vector<T> lis;
    for(auto &p:a){
        typename vector<T>::iterator it;
        //同値許容しない(狭義単調増加)
        it=lower_bound(begin(lis),end(lis),p);
        //同値許容(広義単調増加)
        // it=upper_bound(begin(lis),end(lis),p);
        if(end(lis)==it) lis.push_back(p);
        else *it=p;
    }
    return int(lis.size());
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;cin>>n;
    vector<pair<ll,ll>> v(n);
    rep(i,n){
        ll x,r;cin>>x>>r;
        v[i]=make_pair(x-r,x+r);
    }
    sort(ALL(v));
    reverse(ALL(v));
    vector<ll> a(n);
    rep(i,n) a[i]=v[i].second;
    cout<<LIS(a)<<endl;
    return 0;
}

Submission Info

Submission Time
Task K - ターゲット
User mugen1337
Language C++14 (GCC 5.4.1)
Score 5
Code Size 1335 Byte
Status AC
Exec Time 32 ms
Memory 3832 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 10
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 90, 91
Case Name Status Exec Time Memory
00 AC 32 ms 2560 KB
01 AC 31 ms 2560 KB
02 AC 32 ms 2560 KB
03 AC 29 ms 2560 KB
04 AC 29 ms 2560 KB
05 AC 29 ms 2560 KB
06 AC 21 ms 3832 KB
07 AC 17 ms 2560 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB