Submission #5625305


Source Code Expand

#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H & b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H & b) const { return x == b.x && y == b.y; }
	bool operator!=(const H & b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T & a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T & a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n;
H a[200000];
struct A {
	int x, y;
	bool operator<(A a) {
		if (y != a.y) {
			return y < a.y;
		}
		return x > a.x;
	}
};
A b[200000];
int dp[200000];
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].y;
		b[i] = A{ a[i].x - a[i].y,a[i].x + a[i].y };
	}
	sort(b, b + n);
	for (int i = 1; i <= n; i++) dp[i] = Inf;
	dp[0] = -Inf;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int k = lower_bound(dp, dp + n + 1, -b[i].x) - dp;
		dp[k] = -b[i].x;
		ans = max(ans, k);
	}
	cout << ans << endl;
	
}

Submission Info

Submission Time
Task K - ターゲット
User Thistle
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2667 Byte
Status WA
Exec Time 86 ms
Memory 5760 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 7
WA × 3
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 90, 91
Case Name Status Exec Time Memory
00 AC 86 ms 5760 KB
01 AC 85 ms 5760 KB
02 AC 86 ms 5760 KB
03 WA 69 ms 5760 KB
04 WA 69 ms 5760 KB
05 WA 69 ms 5760 KB
06 AC 53 ms 5760 KB
07 AC 48 ms 5760 KB
90 AC 1 ms 2304 KB
91 AC 1 ms 2304 KB