제출 #1118199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118199		knot222	Inspections (NOI23_inspections)	C++14	11 / 100	28 ms	10732 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(NULL);
    int N,M,S;cin>>N>>M>>S;
    vector<pair<int,int>> ta(M);
    for (int i=0;i<M;i++) {
        cin>>ta[i].first >> ta[i].second;
    }
    
    priority_queue<pair<ll,int>> ss;
    vector<ll> ans(N);
    for (int i=0;i<S;i++) {
        ll t1;
        cin>>t1;
        ss.push(make_pair(t1,i));
    }
    priority_queue<pair<ll,int>> sl;
    //right -> {left, time}
    map<int,pair<int,ll>> range;
    ll tim = 0;
    int sum = 0;
    for (int i=0;i<M;i++) {
        auto it = range.lower_bound(ta[i].first);
        if (it!=range.end()) {
            int l = it->second.first;
            int r = it->first;
            int tt = it->second.second;
            if (l<ta[i].first) {
                range[ta[i].first-1] = {l, tt-(r-ta[i].first)-1};
                it->second.first = ta[i].first;
            }
        }
        while (it!=range.end() && it->first<=ta[i].second) {
            int l = it->second.first;
            int r = it->first;
            int tt = it->second.second;
            sum+=r-l+1;
            //sl.push(make_pair(tim-ta[i].first+r-tt, r-l+1));
            sl.push(make_pair(tim-ta[i].first+r-tt, r-l+1));
            it = range.erase(it);
        }
        if (it!=range.end()) {
            int l = it->second.first;
            int r = it->first;
            int tt = it->second.second;
            if (l<=ta[i].second) {
                sum+=ta[i].second-l+1;
                sl.push(make_pair(tim-ta[i].first+r-tt, ta[i].second-l+1));
                it->second.first = ta[i].second+1;
            }
        }
        tim+=ta[i].second-ta[i].first+1;
        range[ta[i].second] = make_pair(ta[i].first, tim);
    }
    sum=0;
    while (!ss.empty()) {
        while (!ss.empty() && !sl.empty() && ss.top().first<=sl.top().first) {
            sum+=sl.top().second;
            sl.pop();
        }
        ans[ss.top().second] = sum;
        ss.pop();
    }
    for (int i=0;i<S;i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}
/*
5 3 7                                       
1 3
3 5
2 3
0 1 2 3 4 5 6
*/

• Subtask 1: 11 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 23