QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201680#5513. Advertisement 2jmyszka#0 159ms11320kbC++172.6kb2023-10-05 16:05:052024-07-04 02:49:24

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:49:24]
  • 评测
  • 测评结果:0
  • 用时:159ms
  • 内存:11320kb
  • [2023-10-05 16:05:05]
  • 提交

answer

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x) 
#endif
typedef long long ll;
#define pi pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size
constexpr int base = (1 << 19);
int baz = 1;
int tri[2 * base][2];
map<int, int>con;
void upd(int v, int x, int k) {
	v += baz;
	while(v > 0) {
		tri[v][k] = max(tri[v][k], x);
		v /= 2;
	}
}
int que(int l, int r, int k) {
	l += baz;
	r += baz;
	int ans = 0;
	while(l <= r) {
		if(l & 1) {
			ans = max(ans, tri[l][k]);
		}
		if(!(r & 1)) {
			ans = max(ans, tri[r][k]);
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
void solve() {
	//ifstream cin("nazwa.in");
	//ofstream cout("nazwa.out");
	int n;
	cin >> n;
	while(baz <= n) {
		baz *= 2;
	}
	vector<pi>prz;
	for(int i = 1; i <= n; i++) {
		int x, e;
		cin >> x >> e;
		con[x] = 1;
		prz.eb(e, x);
	}
	int k = 1;
	for(auto &[key, val] : con) {
		val = k++;
	}
	sort(all(prz));
	reverse(all(prz));
	//debug(prz);
	int ans = 0;
	for(auto [E, x] : prz) {
		if(que(1, con[x], 0) >= E + x || que(con[x], k, 1) >= E - x) {
			ans++;
			upd(con[x], E + x, 0);
			upd(con[x], E - x, 1);
		}
	}
	cout << ans << '\n';
}
int main() {
	fastio();
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 159ms
memory: 11320kb

input:

128800
9199612 51970557
152303663 51970557
658020283 51970557
305169975 51970557
647937895 51970557
162441995 51970557
664350717 51970557
128813867 51970557
815800777 51970557
422654970 51970557
5325941 51970557
919605369 51970557
775929588 51970557
957253076 51970557
441558150 51970557
730596606 51...

output:

122086

result:

wrong answer 1st lines differ - expected: '116732', found: '122086'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 3600kb

input:

3
231636235 354089104
228392707 930073348
587735804 575683740

output:

1

result:

wrong answer 1st lines differ - expected: '2', found: '1'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%