Submission #5625172


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) {
		if (x + r != b.x + b.r) return x + r < b.x + b.r;
		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);
	int t = 0;
	for (int i = 0; i < n; ) {
		int j = i;
		while (a[i].x + a[i].r == a[j].x + a[j].r)
			j++;
		a[t++] = a[i];
		i = j;
	}
	n = t;
	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 3375 Byte
Status WA
Exec Time 144 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 141 ms 10096 KB
01 WA 144 ms 10096 KB
02 WA 143 ms 10096 KB
03 WA 112 ms 7664 KB
04 WA 112 ms 7664 KB
05 WA 111 ms 7664 KB
06 WA 84 ms 7664 KB
07 AC 80 ms 7664 KB
90 AC 2 ms 2304 KB
91 AC 2 ms 2304 KB