Cod sursa(job #3312303)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 27 septembrie 2025 14:05:59
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

const int NMAX = 5e4;

int n, dx, dy;
int x[NMAX + 1], y[NMAX + 1];
int freq[NMAX + 1];
int freq_left[NMAX + 1], freq_right[NMAX + 2];
int sum_left[NMAX + 1], sum_right[NMAX + 2];

int get_answer(int x[], int dx) {
    for(int i = 0; i <= NMAX; i++) {
        freq[i] = 0;
    }
    for(int i = 1; i <= n; i++) {
        freq[x[i]]++;
    }

    freq_left[0] = freq[0];
    for(int i = 1; i <= NMAX; i++) {
        sum_left[i] = sum_left[i - 1] + freq_left[i - 1];
        freq_left[i] = freq_left[i - 1] + freq[i];
    }

    freq_right[NMAX] = freq[NMAX];
    for(int i = NMAX - 1; i >= 0; i--) {
        sum_right[i] = sum_right[i + 1] + freq_right[i + 1];
        freq_right[i] = freq_right[i + 1] + freq[i];
    }

    int answer = 2e9;
    for(int i = 0; i + dx <= NMAX; i++) {
        answer = min(answer, sum_left[i] + sum_right[i + dx]);
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fin >> n >> dx >> dy;
    for(int i = 1; i <= n; i++) {
        fin >> x[i] >> y[i];
    }
    fout << get_answer(x, dx) + get_answer(y, dy) << '\n';
    return 0;
}