Submission #893364

#	Time	Username	Problem	Language	Result	Execution time	Memory
893364		vjudge1	Inspections (NOI23_inspections)	C++14	100 / 100	295 ms	34992 KiB

Main

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

#define fi first
#define se second

using namespace std;
const int maxn = 2e5 + 5;
int n, m,q;
pair <int, int> a[maxn];
int id[maxn];
long long s[maxn], s1[maxn];
set <pair <int, int>> st;
vector <pair <int, int>> vt;
vector <pair <long long, int>> v;
long long f[maxn];

bool cmp(int i, int j) {
    return s[i]> s[j];
}

int main() {
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i) {
        cin >> a[i].fi >> a[i].se;
        s1[i] = s1[i - 1] + (a[i].se - a[i].fi + 1);
    }
    for(int i = 1; i <= q; ++i) cin >> s[i];
    for(int i = 1; i <= q; ++i) id[i] = i;
    st.insert({1, 0});
    st.insert({n + 1, 0});
    sort(id + 1, id + q + 1, cmp);
    for(int i = 1; i <= m; ++i) {
        vt.clear();
        auto it = st.upper_bound({a[i].fi, m + 1});
        --it;
        int x = 0;
        int y = 0;
        int dx = 0;
        int dy = 0;
        for(it; it != st.end(); ++it) {
            auto r = (*it);
            //cout << i << ' ' << r.fi << ' ' << r.se << '\n';
            if(r.fi < a[i].fi) {
                x = r.fi;
                dx = r.se;
            }
            else if(r.fi >= a[i].se + 1) {
                if(r.fi == a[i].se + 1) break;
                y = r.fi - 1;
                dy = (*(--it)).se;
                break;
            }
            auto it1 = it;
            auto nxt = *(++it1);
            vt.push_back(r);
            int d = r.se;
            if(d == 0) continue;
            if(r.fi < a[i].fi) {
                v.push_back({s1[i - 1] - s1[d] + a[d].se - a[i].fi + 1, min(nxt.fi, a[i].se + 1) - a[i].fi});
            }
            else {
                v.push_back({s1[i - 1] - s1[d] + r.fi - a[i].fi + a[d].se - r.fi + 1, min(nxt.fi, a[i].se + 1) - r.fi});
            }

        }
        for(auto j : vt) {
            st.erase(j);
        }
        if(x) st.insert({x, dx});
        if(y) st.insert({a[i].se + 1, dy});
        st.insert({a[i].fi, i});

    }
    sort(v.begin(), v.end());
    long long res = 0;
    for(int i1 = 1; i1 <= q; ++i1) {
        int i = id[i1];
        while(!v.empty() && v.back().fi > s[i]) {
            res += v.back().se;
            v.pop_back();
        }
        f[i] = res;
    }
    for(int i = 1; i <= q; ++i) cout << f[i] << ' ';

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:13: warning: statement has no effect [-Wunused-value]
   44 |         for(it; it != st.end(); ++it) {
      |             ^~

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