Submission #990887

#	Time	Username	Problem	Language	Result	Execution time	Memory
990887		tincamatei	Advertisement 2 (JOI23_ho_t2)	C++14	10 / 100	318 ms	34676 KiB

Main

#include <bits/stdc++.h>

bool eats(std::pair<int, int> eater, std::pair<int, int> eaten) {
    int dist = std::abs(eater.first - eaten.first);
    return dist <= eater.second - eaten.second;
}

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

    int N;
    std::cin >> N;

    std::set<std::pair<int, int>> ordered;

    std::vector<std::pair<int, int>> input(N);

    for (int i = 0; i < N; i++) {
        int X, E;
        std::cin >> X >> E;
        input[i] = {X, E};
    }

    std::sort(input.begin(), input.end(), [](const std::pair<int, int> a, 
                const std::pair<int, int> b) {
        return a.second < b.second;
    });

    for (int i = 0; i < N; i++) {
        auto [X, E] = input[i];

        std::vector<std::pair<int, int> > to_erase;

        auto split = ordered.lower_bound({X, -1});
        auto it = split;
        
        while (it != ordered.end() && eats({X, E}, *it)) {
            to_erase.push_back(*it);
            it++;
        }

        it = split;
        while (it != ordered.begin() && eats({X, E}, *it)) {
            it--;
            if (eats({X, E}, *it))
                to_erase.push_back(*it);
        }

        for (auto it: to_erase)
            ordered.erase(it);
        ordered.insert({X, E});
    }

    std::cout << ordered.size();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         auto [X, E] = input[i];
      |              ^

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