제출 #914148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914148		esomer	Inspections (NOI23_inspections)	C++17	22 / 100	470 ms	39108 KiB

Main

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

#define int long long

vector<pair<int, int>> queries;
vector<long long> prefix;
vector<long long> substract;
vector<pair<int, int>> safety;
long long totalSum = 0;

long long sum(int l, int r){
    if(l > r) return 0;
    if(l > 0) return prefix[r] - prefix[l-1];
    else return prefix[r];
}

long long getDist(int i, int j, int ind){
    assert(i <= j);
    long long mid = sum(i+1, j-1);
    return mid + queries[i].second - ind + ind - queries[j].first;
}

void add(long long dist, int val){
    int lo = 0;
    int hi = (int)safety.size() - 1;
    int bst = (int)safety.size();
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(safety[mid].first > dist){
            bst = mid;
            hi = mid - 1;
        }else lo = mid + 1;
    }
    // cout << "add: dist " << dist << " val "<< val << " bst "<< bst << "\n";
    totalSum += val;
    substract[bst] += val;
}

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> start(n), ends(n+1);
    queries.resize(m); prefix.resize(m);
    for(int i = 0; i < m; i++){
        int l, r; cin >> l >> r; l--; r--;
        start[l].push_back(i);
        ends[r+1].push_back(i);
        if(i == 0) prefix[i] = r - l + 1;
        else prefix[i] = prefix[i-1] + r - l + 1;
        queries[i] = {l, r};
    }
    safety.resize(q);
    substract.assign(q+1, 0);
    for(int i = 0; i < q; i++){
        int s; cin >> s;
        safety[i] = {s, i};
    }
    sort(safety.begin(), safety.end());
    set<pair<int, long long>> s;
    for(int i = 0; i < n; i++){
        // cout << "i "<< i << " add "<< endl;
        for(int x : start[i]){
            if(s.empty()){
                s.insert({x, -1});
                add(-1, n-i);
                continue;
            }
            auto it = s.lower_bound({x, -1});
            if(it == s.end()){
                it--;
                long long dist = getDist((*it).first, x, i);
                add(dist, n-i);
                s.insert({x, dist});
            }else if(it == s.begin()){
                int y = (*it).first;
                long long dist = getDist(x, y, i);
                add(dist, n-i);
                s.erase(it);
                s.insert({y, dist});
            }else{
                pair<int, long long> tp = (*it);
                it--;
                pair<int, long long> btm = (*it);
                s.erase(tp);
                add(tp.second, -(n-i));
                long long distTpMe = getDist(x, tp.first, i);
                long long distMeBtm = getDist(btm.first, x, i);
                add(distTpMe, n-i);
                add(distMeBtm, n-i);
                s.insert({x, distMeBtm});
                s.insert({tp.first, distTpMe});
            }
        }
        // cout << "remove"<< endl;
        for(int x : ends[i]){
            auto it = s.lower_bound({x, -1});
            pair<int, long long> p = *it;
            add(p.second, -(n-i));
            int prev = -1, nxt = -1;
            if(it != s.begin()){
                it--;
                prev = (*it).first;
            }
            s.erase(p);
            it = s.lower_bound({x, -1});
            if(it != s.end()){
                nxt = (*it).first;
            }
            if(nxt != -1){
                it = s.lower_bound({nxt, -1});
                add((*it).second, -(n-i));
                s.erase(it);
                if(prev == -1){
                    s.insert({nxt, -1});
                    add(-1, n-i);
                }else{
                    long long dist = getDist(prev, nxt, i);
                    s.insert({nxt, dist});
                    add(dist, n-i);
                }
            }
        }
    }
    vector<long long> ans(q);
    for(int i = 0; i < q; i++){
        totalSum -= substract[i];
        ans[safety[i].second] = totalSum;
    }
    for(long long& x : ans) cout << x << " ";
    cout << "\n";
}

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

    // int tt; cin >> tt;
    int tt = 1;
    while(tt--) solve();
}

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