Submission #782372

#TimeUsernameProblemLanguageResultExecution timeMemory
782372thimote75Advertisement 2 (JOI23_ho_t2)C++14
100 / 100
130 ms19832 KiB

#include <bits/stdc++.h>

using namespace std;

using  pii = pair<int, int>;
using vpii = vector<pii>;

bool forces (pii parent, pii child) {
    int dx = abs(parent.first - child.first);
    int dE = parent.second - child.second;

    return dx <= dE;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vpii people_array;
    for (int i = 0; i < N; i ++) {
        int x, E;
        cin >> x >> E;

        people_array.push_back({ x, E });
    }

    sort(people_array.begin(), people_array.end());

    vpii stack;
    for (pii man : people_array) {
            if (stack.size() != 0 && forces(stack.back(), man)) continue ;

        while (stack.size() != 0 && forces(man, stack.back())) stack.pop_back();
        stack.push_back(man);
    }

    cout << stack.size() << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...