제출 #857011

#제출 시각아이디문제언어결과실행 시간메모리
857011jmyszka2007Advertisement 2 (JOI23_ho_t2)C++17
59 / 100
2051 ms29900 KiB
#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 + 1) { 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); debug(a, b); 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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...