QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201690 | #5513. Advertisement 2 | jmyszka# | 10 | 906ms | 36392kb | C++17 | 2.7kb | 2023-10-05 16:09:13 | 2024-07-04 02:16:47 |
Judging History
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();
}
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 182ms
memory: 12948kb
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: 195ms
memory: 13708kb
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: 314ms
memory: 17284kb
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: 172ms
memory: 15972kb
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: 906ms
memory: 36392kb
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: 590ms
memory: 25444kb
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: 345ms
memory: 16168kb
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: 258ms
memory: 15780kb
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: 3544kb
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%