Submission #1136127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136127		fzyzzz_z	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	109 ms	8568 KiB

Main

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

int32_t main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 

    int n; 
    cin >> n; 
    vector<pair<int, int>> a(n); 
    for (auto & [x, y]: a) {
        cin >> x >> y; 

        auto x1 = x - y; 
        auto y1 = x + y; 

        x = x1; 
        y = y1; 
    }

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

    // find upper hull 
    vector<pair<int, int>> b; 
    for (auto [x, y]: a) {
        if (b.size() && b.back().first == x && b.back().second <= y) b.pop_back(); 
        if (!b.size() || y > b.back().second) b.push_back({x, y}); 
    }

    cout << b.size() << '\n'; 


    return 0; 
}

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