Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <unordered_set>
- #include <map>
- #include <unordered_map>
- #include <set>
- #include <numeric>
- #include <iomanip>
- #define ll int64_t
- #define vll vector<int64_t>
- #define vd vector<double>
- #define ld long double
- #define forin(i, a, n) for (int64_t i = a; i < n; ++i)
- #define forn(i, n) for (int64_t i = 0; i < n; ++i)
- #define pb push_back
- #define eb emplace_back
- using namespace std;
- //void build(vector<int> &t, vector<pair<int, int>> &pallets, int v, int l, int r) {
- // if (r - l == 1)
- // t[v] = pallets[l].second;
- // else {
- // int m = (l + r) / 2;
- // build(t, pallets, v * 2 + 1, l, m);
- // build(t, pallets, v * 2 + 2, m, r);
- // t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
- // }
- //}
- void build(vector<int> &t, vector<pair<int, int>> &pallets, int n) {
- forn(i, n) {
- t[n - 1 + i] = pallets[i].second;
- }
- for (int i = n - 2; i >= 0; --i) {
- t[i] = max(t[i * 2 + 1], t[i * 2 + 2]);
- }
- }
- //int find_max(vector<int> &t, int v, int tl, int tr, int l, int r) {
- // if (tl < l || tr > r)
- // return INT32_MIN;
- // if (l >= tl && r <= tr)
- // return t[v];
- // int tm = (tl + tr) / 2;
- // return max(find_max(t, v * 2 + 1, tl, tm, l, min(r, tm)),
- // find_max(t, v * 2 + 2, tm, tr, max(l, tm), r));
- //}
- int find_max(vector<int> &t, int left, int right) {
- int left_res = INT32_MIN;
- int right_res = INT32_MIN;
- while (left < right) {
- if (left % 2 == 0) {
- left_res = max(left_res, t[left]);
- }
- left /= 2;
- if (right % 2 == 1) {
- right_res = max(right_res, t[right]);
- }
- right /= 2;
- }
- if (left == right) {
- left_res = max(left_res, t[left]);
- }
- return max(left_res, right_res);
- }
- //int bin_search(vector<pair<int, int>> &pallets, int len) {
- // int l = -1;
- // int r = pallets.size();
- // while (l < r - 1) {
- // int m = (l + r) / 2;
- // if (pallets[m].first < len) {
- // l = m + 1;
- // } else {
- // r = m;
- // }
- // }
- //
- // return r + 1;
- //}
- int main() {
- cin.tie(nullptr);
- cout.tie(nullptr);
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- vector<pair<int, int>> pallets;
- forn(i, n) {
- int a, b;
- cin >> a >> b;
- int _min = min(a, b);
- int _max = max(a, b);
- pallets.emplace_back(_min, _max);
- }
- sort(pallets.begin(), pallets.end());
- vector<int> lengths;
- for (auto pallet : pallets) {
- lengths.push_back(pallet.first);
- }
- int size = n * 4 - 1;
- vector<int> t(size, INT32_MIN);
- build(t, pallets, n);
- // build(t, pallets, 0, 0, size);
- int good = 0;
- forn(i, n) {
- int len = pallets[i].first;
- int width = pallets[i].second;
- auto iter = upper_bound(lengths.begin(), lengths.end(), len);
- if (iter == lengths.end()) {
- continue;
- }
- int v = iter - lengths.begin();
- int max_width = find_max(t, size - n * 2 + v, size);
- if (max_width > width) {
- ++good;
- }
- }
- cout << n - good;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement