Submission #1320523

#TimeUsernameProblemLanguageResultExecution timeMemory
1320523laykLightning Rod (NOI18_lightningrod)C++20
100 / 100
968 ms442464 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <immintrin.h>

#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
//
using ld = long double;
using ll = int;
using i128 = __int128;
using ull = unsigned long long;
using pll = std::pair<ll, ll>;
using cmpl = std::complex<ld>;
template<typename T>
using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr ll MOD1 = 998244353;
constexpr ll MOD = 1000000007;
constexpr ll INV2 = 499122177;
constexpr ld PI = 3.141592653589793;
const ld eps = 1e-7;
const ll K = 3;
//const ll C = 200;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

ld START_TIME = clock();

bool cmp(pll a, pll b) {
    return (a.first < b.first) || ((a.first == b.first) && (a.second > b.second));
}

pll a[10000001];

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9')
        ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}

void solve() {
    ll n = readInt();
    for (int i = 0; i < n; ++i) {
        ll x = readInt(), y = readInt();
        a[i].first = x - y + 1000000000, a[i].second = x + y;
    }
    ll c = 1ll << 16, l = 0;
    std::vector<std::vector<pll>> inds(c);
    for (int i = 0; i < n; ++i) {
        inds[a[i].second % c].push_back(a[i]);
    }
    l = 0;
    for (int i = 0; i < c; ++i) {
        for (auto u : inds[i]) {
            a[l++] = (u);
        }
        inds[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        inds[a[i].second / c].push_back(a[i]);
    }
    l = 0;
    for (int i = c - 1; i >= 0; --i) {
        std::reverse(inds[i].begin(), inds[i].end());
        for (auto u : inds[i]) {
            a[l++] = (u);
        }
        inds[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        inds[a[i].first % c].push_back(a[i]);
    }
    l = 0;
    for (int i = 0; i < c; ++i) {
        for (auto u : inds[i]) {
            a[l++] = u;
        }
        inds[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        inds[a[i].first / c].push_back(a[i]);
    }
    l = 0;
    for (int i = 0; i < c; ++i) {
        for (auto u : inds[i]) {
            a[l++] = u;
        }
        inds[i].clear();
    }
    ll ans = 0;
    ll max = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i].second > max) {
            max = std::max(max, a[i].second);
            ++ans;
        }
    }
    std::cout << ans;
}

signed main() {
#ifdef DEBUG
    std::freopen("/home/anton/CLionProjects/untitled/input.txt", "r", stdin);
#else
    //    std::freopen("tri.in", "r", stdin); std::freopen("tri.out", "w", stdout);
#endif
    std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false);
    int tt = 1;
//    std::cin >> tt;
    while (tt--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << '\n';
    ld TIME = (clock() - START_TIME) / CLOCKS_PER_SEC;
    std::cerr << "Time: " << TIME << '\n';
#endif
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...