QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201694#5513. Advertisement 2jmyszka#10 999ms36572kbC++172.7kb2023-10-05 16:11:532024-07-04 02:16:47

Judging History

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

  • [2024-07-04 02:16:47]
  • 评测
  • 测评结果:10
  • 用时:999ms
  • 内存:36572kb
  • [2023-10-05 16:11:53]
  • 提交

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 = -2e9;
	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;
	}
	for(int i = 0; i < 2 * baz; i++) {
		tri[i][0] = -2e9;
		tri[i][1] = -2e9;
	}
	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));
	int ans = 0;
	for(auto [E, x] : prz) {
		int a = que(1, con[x], 0), b = que(con[x], k, 1);
		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: 10
Accepted

Test #1:

score: 10
Accepted
time: 208ms
memory: 11900kb

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:

116732

result:

ok single line: '116732'

Test #2:

score: 0
Accepted
time: 226ms
memory: 12652kb

input:

178516
481507914 185523732
434623365 185523732
472444125 185523732
759573017 185523732
253426284 185523732
700756636 185523732
74218273 185523732
978855318 185523732
193027753 185523732
670445963 185523732
647115447 185523732
355737335 185523732
213219833 185523732
580124162 185523732
361750049 1855...

output:

77180

result:

ok single line: '77180'

Test #3:

score: 0
Accepted
time: 340ms
memory: 17336kb

input:

462572
101498948 303922224
642297835 303922224
417145698 303922224
889349783 303922224
434461522 303922224
93863358 303922224
215632530 303922224
832856402 303922224
703199983 303922224
809081237 303922224
557497978 303922224
655494326 303922224
195187810 303922224
812819691 303922224
814441567 3039...

output:

4625

result:

ok single line: '4625'

Test #4:

score: 0
Accepted
time: 180ms
memory: 17236kb

input:

325752
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840273835
619184372 840...

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 999ms
memory: 36572kb

input:

500000
432233751 37126744
876209848 37126744
115636122 37126744
722895189 37126744
385407335 37126744
631777770 37126744
640127217 37126744
850533001 37126744
857281519 37126744
47214872 37126744
67273107 37126744
817606002 37126744
197019377 37126744
816304624 37126744
780928469 37126744
991314112 ...

output:

453173

result:

ok single line: '453173'

Test #6:

score: 0
Accepted
time: 741ms
memory: 25392kb

input:

500000
347979517 402569575
240027608 402569575
984267933 402569575
490577061 402569575
248258763 402569575
866530973 402569575
301265202 402569575
736701829 402569575
47460490 402569575
878566519 402569575
485021670 402569575
978430003 402569575
530094575 402569575
51797713 402569575
975446346 40256...

output:

216136

result:

ok single line: '216136'

Test #7:

score: 0
Accepted
time: 376ms
memory: 16452kb

input:

500000
394843641 428581569
931365318 428581569
205656498 428581569
325306857 428581569
567772605 428581569
495792279 428581569
521260039 428581569
275722970 428581569
168204637 428581569
882738248 428581569
211294121 428581569
236121938 428581569
498382424 428581569
406387147 428581569
664092862 428...

output:

5000

result:

ok single line: '5000'

Test #8:

score: 0
Accepted
time: 283ms
memory: 16776kb

input:

500000
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502907510
180068482 502...

output:

1

result:

ok single line: '1'

Subtask #2:

score: 0
Wrong Answer

Test #9:

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

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:

100%
Accepted

Dependency #2:

0%