Submission #854576

#	Time	Username	Problem	Language	Result	Execution time	Memory
854576		biximo	Inspections (NOI23_inspections)	C++17	0 / 100	153 ms	21720 KiB

Main

#include <bits/stdc++.h>
using namespace std;
map<long long, long long> cnts;
int n, m, q, len = 1<<18;
long long tree[1<<19] = {0};
bool isThere[1 << 19] = {0};
void query(int a, int b, long long v, int x, int y, int p) {
    long long t = v + x - a;
    if(tree[p]) {
//        cout << x << " " << y << " " << t << "\n";
        cnts[t - tree[p] - 1] += (y - x + 1);
        tree[p] = 0;
    } else {
        if(x == y) return;
        int z = (x + y) >> 1;
        query(a, b, v, x, z, p * 2);
        query(a, b, v, z + 1, y, p * 2 + 1);
    }
}
void update(int a, int b, long long v, int x=0, int y=len-1, int p=1) {
    if(a > y || b < x) return;
    int z = (x + y) >> 1;
    if(a <= x && b >= y) {
        long long t = v + x - a;
        isThere[p] = 1;
        if(tree[p]) {
//            cout << x << " " << y << " " << t << "\n";
            cnts[t - tree[p] - 1] += (y - x + 1);
        } else {
            if(x != y) {
                query(a, b, v, x, z, p * 2);
                query(a, b, v, z + 1, y, p * 2 + 1);
                isThere[p] = isThere[p * 2] || isThere[p * 2 + 1];
            }
        }
        tree[p] = t;
        return;
    }
    if(tree[p]) {
        tree[p * 2] = tree[p];
        tree[p * 2 + 1] = tree[p] + (z - x + 1);
        tree[p] = 0;
    }
    update(a, b, v, x, z, p * 2);
    update(a, b, v, z + 1, y, p * 2 + 1);
    isThere[p] = isThere[p * 2] || isThere[p * 2 + 1];
}
using pi = pair<long long, int>;
long long ans[200000], pref[50000005];
vector<pi> qs;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    long long time = 1;
    while(m--) {
        int a, b;
        cin >> a >> b;
        update(a, b, time);
        time += b - a + 1;
    }
    qs.resize(q);
    for(int i = 0; i < q; i ++) {
        cin >> qs[i].first;
        qs[i].second = i;
        if(cnts[qs[i].first] == 0) cnts.insert({qs[i].first, 0});
//        cnts[qs[i].first] += 0;
    }
    assert(cnts.size() < 50000005);
    sort(qs.begin(), qs.end());
    int ind = 1, pt = 0;
    for(auto&[a, b]: cnts) {
        pref[ind] += b;
        ind ++;
    }
    for(int i = 0; i < cnts.size(); i ++) {
        pref[i + 1] += pref[i];
    }
    ind = 1;
    for(auto&[a, b]: cnts) {
        if(pt < q && qs[pt].first == a) {
            ans[qs[pt].second] = pref[cnts.size()] - pref[ind - 1];
            pt ++;
        }
        ind ++;
    }
    for(int i = 0; i < q; i ++) cout << ans[i] << " ";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < cnts.size(); i ++) {
      |                    ~~^~~~~~~~~~~~~

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