제출 #1146749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146749		bobbilyking	Inspections (NOI23_inspections)	C++20	100 / 100	471 ms	43164 KiB

Main

// o3 code

#include <bits/stdc++.h>
using namespace std;
 
// We'll use 1-indexed arrays for machines and tasks.
 
// Data structure for segment tree (with lazy propagation)
// Each leaf corresponds to one machine’s "last-run" value (an integer in [0,m]).
// Our segment tree supports range updates (setting a whole interval to a given value)
// and range queries: we want to “collect” contiguous blocks of uniform value.
 
struct Node {
    int l, r;
    bool uniform; // true if the entire segment is set to a single value
    int val;     // the value if uniform (the "last-run" value)
};
 
// Global segment tree array.
vector<Node> segTree;
int n; // number of machines; will be set in main
 
// Build the segment tree over [l, r] (machine indices)
void build(int idx, int l, int r) {
    segTree[idx].l = l;
    segTree[idx].r = r;
    segTree[idx].uniform = true;
    segTree[idx].val = 0;  // initially no machine has been run
    if(l < r){
        int mid = (l + r) / 2;
        build(idx*2, l, mid);
        build(idx*2+1, mid+1, r);
    }
}
 
// Push down lazy update: if current node is uniform, propagate to children.
void pushDown(int idx) {
    if(!segTree[idx].uniform) return; // nothing to push
    if(segTree[idx].l == segTree[idx].r) return; // leaf, nothing to do
    int val = segTree[idx].val;
    // Set children uniformly to this value
    segTree[idx*2].uniform = true;
    segTree[idx*2].val = val;
    segTree[idx*2+1].uniform = true;
    segTree[idx*2+1].val = val;
}
 
// Range update: set all machines in [L, R] to new_val.
void updateRange(int idx, int L, int R, int new_val) {
    int l = segTree[idx].l, r = segTree[idx].r;
    if(R < l || r < L) return; // no overlap
    if(L <= l && r <= R) {
        segTree[idx].uniform = true;
        segTree[idx].val = new_val;
        return;
    }
    // Otherwise, push down the lazy value (if any)
    pushDown(idx);
    // Recurse
    updateRange(idx*2, L, R, new_val);
    updateRange(idx*2+1, L, R, new_val);
    // After update, check if children are uniform and equal.
    if(segTree[idx*2].uniform && segTree[idx*2+1].uniform &&
       segTree[idx*2].val == segTree[idx*2+1].val) {
        segTree[idx].uniform = true;
        segTree[idx].val = segTree[idx*2].val;
    } else {
        segTree[idx].uniform = false;
    }
}
 
// We want to query the range [L,R] and return a vector of pairs (p, count)
// where the interval [L,R] is partitioned into contiguous blocks that are uniform,
// each with value p (the "last-run" value) and block length = count.
 
void queryRange(int idx, int L, int R, vector<pair<int,int>> &res) {
    int l = segTree[idx].l, r = segTree[idx].r;
    if(R < l || r < L) return; // no overlap
    if(L <= l && r <= R && segTree[idx].uniform) {
        // Entire segment is uniform.
        res.push_back({segTree[idx].val, r - l + 1});
        return;
    }
    // Otherwise, push down and combine children.
    pushDown(idx);
    queryRange(idx*2, L, R, res);
    queryRange(idx*2+1, L, R, res);
}
 
// To merge contiguous blocks in the result vector.
void mergeResult(vector<pair<int,int>> &v) {
    if(v.empty()) return;
    vector<pair<int,int>> tmp;
    tmp.push_back(v[0]);
    for (size_t i=1; i<v.size(); i++){
        if(v[i].first == tmp.back().first)
            tmp.back().second += v[i].second;
        else
            tmp.push_back(v[i]);
    }
    v.swap(tmp);
}
 
// Main
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, q;
    cin >> n >> m >> q;
    // tasks: store as 1-indexed arrays. For task i (1 <= i <= m), we have:
    // l[i] and r[i]
    vector<int> taskL(m+1), taskR(m+1);
    for (int i = 1; i <= m; i++){
        cin >> taskL[i] >> taskR[i];
    }
 
    // Precompute D[0..m]: D[i] = total number of machine runs in tasks 1..i.
    // Let D[0]=0.
    vector<long long> D(m+1,0);
    for (int i = 1; i <= m; i++){
        long long runs = (long long)taskR[i] - taskL[i] + 1;
        D[i] = D[i-1] + runs;
    }
 
    // Allocate segment tree. For n machines, we need up to 4*n nodes.
    segTree.resize(4 * (n + 1));
    build(1, 1, n);
 
    // We'll accumulate frequencies of "gap" values.
    // Each time a machine j is updated in a task i (if it had a previous run in task p != 0),
    // we add an event with gap = (D[i-1]-D[p-1]) - (taskL[i] - taskL[p]) - 1.
    // We sum the counts for each gap.
    unordered_map<long long, long long> freq;
    freq.reserve(m*2);
 
    // Process tasks in order.
    for (int i = 1; i <= m; i++){
        int L = taskL[i], R = taskR[i];
        vector<pair<int,int>> queryRes;
        queryRange(1, L, R, queryRes);
        mergeResult(queryRes);
        // For every contiguous block in [L,R] with uniform last-run value p,
        // if p != 0 then for all machines in that block, an inspection is needed now.
        for (auto &pcount : queryRes) {
            int p = pcount.first;
            int cnt = pcount.second;
            if(p != 0){
                // Compute gap = (D[i-1]-D[p-1]) - (taskL[i] - taskL[p]) - 1.
                // Note: taskL[p] is defined because p>=1.
                long long gap = (D[i-1] - D[p-1]) - ((long long)taskL[i] - taskL[p]) - 1;
                freq[gap] += cnt;
            }
        }
        // Now update machines in [L,R]: set their last-run value to i.
        updateRange(1, L, R, i);
    }
 
    // At this point, the total number of inspections (if safety value s=0)
    // equals the sum over all events, i.e. total frequency.
    // For a candidate safety value s, we need to count only those events
    // with gap >= s.
    // We now “compress” the frequency table into a sorted vector.
    vector<pair<long long,long long>> events;
    events.reserve(freq.size());
    for (auto &pr : freq) {
        events.push_back({pr.first, pr.second});
    }
    sort(events.begin(), events.end());
 
    // Build suffix sums: for each index i in events, let suff[i] = sum_{j >= i} events[j].second.
    int k = events.size();
    vector<long long> suff(k+1, 0);
    for (int i = k-1; i >= 0; i--){
        suff[i] = suff[i+1] + events[i].second;
    }
 
    // Answer the queries.
    // We read q candidate safety values s, and for each, output
    // the number of events (inspections) that happen if safety value = s.
    // (i.e. count of events with gap >= s)
    vector<long long> ans(q, 0);
    for (int i = 0; i < q; i++){
        long long sVal;
        cin >> sVal;
        // Binary search in events for the first event with gap >= sVal.
        int lo = 0, hi = k;
        while(lo < hi){
            int mid = (lo + hi) / 2;
            if(events[mid].first >= sVal) hi = mid;
            else lo = mid + 1;
        }
        long long tot = (lo < k ? suff[lo] : 0LL);
        ans[i] = tot;
    }
 
    // Output answers in one line.
    for (int i = 0; i < q; i++){
        cout << ans[i] << (i+1==q? "\n" : " ");
    }
    return 0;
}

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