제출 #1326558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326558		Bolatulu	Inspections (NOI23_inspections)	C++20	100 / 100	993 ms	145272 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define md ((tl + tr) >> 1)
#define TL v + v, tl, md
#define TR v + v + 1, md + 1, tr
#define int ll

const int maxn = 1e6 + 7;

int n, m, q, t[4 * maxn], p[4 * maxn], ans[maxn], L[maxn], R[maxn], sum[maxn];
vector<pair<int, int>> sv;

void push(int v) {
    if (p[v] != -1) {
        t[v + v] = p[v];
        t[v + v + 1] = p[v];
        p[v + v] = p[v];
        p[v + v + 1] = p[v];
        p[v] = -1;
    }
}

void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n) {
    if (t[v] != -1 && tl >= l && tr <= r) {
        if (t[v] != 0)
            sv.emplace_back(sum[x] - L[x] - (sum[t[v]] - L[t[v]]), tr - tl + 1);
        t[v] = x;
        p[v] = x;
        return;
    }
    if (tl > r || l > tr)
        return;

    push(v);
    upd(l, r, x, TL), upd(l, r, x, TR);

    if (t[v + v] != t[v + v + 1])
        t[v] = -1;
    else
        t[v] = t[v + v];
}

void solve() {
    cin >> n >> m >> q;
    
    for (int i = 1; i <= m; i++) {
        cin >> L[i] >> R[i];

        upd(L[i], R[i], i);

        sum[i + 1] = sum[i] + R[i] - L[i] + 1;
    }
    sort(all(sv));
    reverse(all(sv));

    // for (auto x : sv)
    //     cout << x.first << ' ';
    // cout << endl;

    vector<pair<int, int>> sq(q);
    for (int i = 0; i < q; i++)
        cin >> sq[i].first, sq[i].second = i;
    sort(all(sq));
    reverse(all(sq));

    int p = -1, res = 0;
    for (int i = 0; i < q; i++) {
        while (p + 1 < sv.size() && sv[p + 1].first > sq[i].first) p++, res += sv[p].second;
        
        ans[sq[i].second] = res;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << ' ';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) {
        solve();
        // cout << '\n';
    }
    return 0;
}

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