Submission #5625061


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[200000];
vector<int>v;
int dat[200000];
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 3168 Byte
Status RE
Exec Time 258 ms
Memory 6128 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 2
WA × 3
RE × 5
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 90, 91
Case Name Status Exec Time Memory
00 RE 258 ms 6128 KB
01 WA 139 ms 6000 KB
02 RE 238 ms 6000 KB
03 WA 121 ms 5744 KB
04 WA 121 ms 5744 KB
05 RE 217 ms 5744 KB
06 RE 181 ms 5744 KB
07 RE 174 ms 5744 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB