Submission #1169679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169679		nathan4690	Inspections (NOI23_inspections)	C++20	100 / 100	720 ms	32368 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name "TEST"
using namespace std;
const ll maxn=1e6+5, inf=1e18;

int n, m, q;
set<pair<int, ll>> S;
map<ll,ll> mp;
vector<pair<ll,ll>> ans;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp", "r", stdin);
        freopen(__file_name ".out", "w", stdout);
    }
    // code here
    cin >> n >> m >> q;
    f1(i,n){
        S.insert({i, inf-1});
    }
    S.insert({n+1, -1LL});
    ll tim = 1;
    f1(i,m){
        int l, r; cin >> l >> r;
        ll rtim = tim - (l - 1);
        auto it_l = S.lower_bound(make_pair(l, inf));
//        for(auto item: S) cout << "! " << item.first << ' ' << item.second << endl;
//        cout << endl;
        assert(it_l != S.begin());
        it_l = prev(it_l);
        auto it_r = S.upper_bound(make_pair(r, inf));
        pair<int, ll> add_le = {-1, -1}, add_ri = {-1, -1};
        if(it_l->first < l){
            add_le = *it_l;
        }
        while(it_l != it_r){
            int le = it_l->first;
            ll pretime = it_l->second;
            if(next(it_l) == it_r && r + 1 != next(it_l)->first){
                add_ri = {r+1, it_l->second};
            }
            it_l = S.erase(it_l);
            int ri = (it_l->first) - 1;
            le = max(le, l);
            ri = min(ri, r);
            mp[rtim - pretime - 1] += ri - le + 1;
        }
        if(add_le.first != -1){
            S.insert(add_le);
        }
        if(add_ri.first != -1) S.insert(add_ri);
        S.insert({l, rtim});
        tim += r - l + 1;
    }
    ll sum = 0;
    while(!mp.empty()){
        sum += mp.rbegin()->second;
        ans.push_back(make_pair(mp.rbegin()->first, sum));
        mp.erase(prev(mp.end()));
    }
    reverse(ans.begin(), ans.end());
    while(q--){
        ll s; cin >> s;
        auto it = lower_bound(ans.begin(), ans.end(), make_pair(s, -inf));
        if(it == ans.end()) cout << 0;
        else cout << it->second;
        cout << ' ';
    }
//    for(auto item: mp) cout << "ans: " << item.first << ' ' << item.second << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(__file_name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(__file_name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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