Submission #1271863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271863		soab	Inspections (NOI23_inspections)	C++20	29 / 100	72 ms	18596 KiB

Main

// soab

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define nl '\n'
#define fi first
#define se second

void io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}   

const int maxn = 2 * 1e5 + 1;

int n, m, t;
int l[maxn], r[maxn], q[maxn];

void sub2() {
    vector<int> last(n + 1, 0), v;
    vector<bool> vis(n + 1, 0);
    int day = 1;

    for(int i = 0; i < m; i++) {
        for(int j = l[i]; j <= r[i]; j++) {
            if(!vis[j]) vis[j] = 1;
            else {
                v.push_back(day - last[j] - 1);
            }
            last[j] = day;
            day++;
        }
    }  

    int s = v.size();
    sort(v.begin(), v.end());

    for(int i = 0; i < t; i++) {
        int st = lower_bound(v.begin(), v.end(), q[i]) - v.begin();
        cout << s - st << ' ';
    }
}


signed main() {
    io();

    cin >> n >> m >> t;
    for(int i = 0; i < m; i++) cin >> l[i] >> r[i];
    for(int i = 0; i < t; i++) cin >> q[i];
    
    if(n <= 2000 && m <= 2000) {
        sub2();
    }

    return 0;
}   

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