Submission #782372

#	Time	Username	Problem	Language	Result	Execution time	Memory
782372		thimote75	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	130 ms	19832 KiB

Main

#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";
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31