Submission #5625096


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;
struct A {
	int x, r;
	bool operator<(A b) {
		return x + r < b.x + b.r;
	}
};
A a[1000000];
vector<int>v;
int dat[1000000];
int m = 1;
void update(int x, int t) {
	x += m - 1;
	dat[x] = t;
	while (x > 0) {
		x = (x - 1) / 2;
		dat[x] = max(dat[x + 2 + 1], dat[x * 2 + 2]);
	}
}
int query(int i, int a, int b, int l, int r) {
	if (b <= l || r <= a) return 0;
		if (a <= l && r <= b) {
			return dat[i];
		}
	return max(query(i * 2 + 1, a, b, l, (l + r) / 2),
		query(i * 2 + 2, a, b, (l + r) / 2, r));
}
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].r;
		v.push_back(a[i].x + a[i].r);
		v.push_back(a[i].x - a[i].r);
	}
	sort(a, a + n);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	while (m < n) m *= 2;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int s = upper_bound(all(v), a[i].x - a[i].r) - v.begin();
		int e = lower_bound(all(v), a[i].x - a[i].r) - v.begin();
		int k = query(0, s, m, 0, m);
		ans = max(ans, k + 1);
		update(e, k + 1);
	}
	cout << ans << endl;
}

Submission Info

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

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 3
WA × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 90, 91
Case Name Status Exec Time Memory
00 WA 140 ms 10096 KB
01 WA 141 ms 10096 KB
02 WA 140 ms 10096 KB
03 WA 121 ms 7664 KB
04 WA 121 ms 7664 KB
05 WA 120 ms 7664 KB
06 WA 83 ms 7664 KB
07 AC 78 ms 7664 KB
90 AC 2 ms 2304 KB
91 AC 2 ms 2304 KB