Submission #1356797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356797		nathlol2	Monsters (NOI25_monsters)	C++20	100 / 100	137 ms	23956 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define sc second
using namespace std;
const int N = 2e5 + 5, INF = 2e9;
int n, k, ans, x[N];
pair<int, int> a[N];
set<int> s;
unordered_map<int, int> v;

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

    cin >> n >> k;
    for(int i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    for(int i = 1;i<=k;i++) cin >> x[i], s.insert(x[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1;i<=n;i++){
        auto it = s.lower_bound(a[i].fi);
        int l = -INF, r = INF;
        if(it != s.end()) r = *it;
        if(it != s.begin()){
            --it;
            l = *it;
        }
        if(min(r - a[i].fi, a[i].fi - l) >= a[i].sc) ans += a[i].sc;
        else{
            ans += min(r - a[i].fi, a[i].fi - l);
            if(r - a[i].fi == a[i].fi - l){
                if(!v[l] && !v[r]){
                    v[r] = 1;
                    ++ans;
                }
            }else if(a[i].fi - l < r - a[i].fi){
                if(!v[l]) v[l] = 1, ++ans;
            }else{
                if(!v[r]) v[r] = 1, ++ans;
            }
        }
    }
    cout << ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 30 / 30
• Subtask 5: 29 / 29
• Subtask 6: 11 / 11