QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201680 | #5513. Advertisement 2 | jmyszka# | 0 | 159ms | 11320kb | C++17 | 2.6kb | 2023-10-05 16:05:05 | 2024-07-04 02:49:24 |
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 = 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%