Submission #1102321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102321		thangdz2k7	Inspections (NOI23_inspections)	C++17	100 / 100	290 ms	34152 KiB

Main

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, q, lo;
set <ii> s;
long long last[N];
vector <pair <long long, int>> e;

void add(long long u, int val){
    e.emplace_back(u, val + q);
    //cout << lo << ' ' << u << ' ' << val << endl;
}

void solve(){
    cin >> n >> m >> q;
    s.insert({1, n});

    long long timer = 0;
    for (lo = 1; lo <= m; ++ lo){
        int l, r; cin >> l >> r;
        for (auto it = s.lower_bound({l, l}); it != s.end();){
            auto [u, v] = *it;
            if (u > r) break;
            it = s.erase(it);
            if (v <= r){
                if (last[u])
                    add(timer + u - l - last[u], v - u + 1);
            }
            else {
                if (last[u]) add(timer + u - l - last[u], r - u + 1);
                s.insert({r + 1, v});
                if (last[u]) last[r + 1] = last[u] + (r - u + 1);
                break;
            }
        }

        last[l] = timer + 1;
        s.insert({l, r});
        if (l > 1){
            auto [u, v] = *(--s.lower_bound({l, l}));
            if (v >= l && v <= r){
                if (last[u]) add(timer - (last[u] + l - u), v - l + 1);
                s.erase({u, v}); s.insert({u, l - 1});
            }
            else if (v >= l){
                if (last[u]) add(timer - (last[u] + l - u), r - l + 1);
                s.erase({u, v}); s.insert({u, l - 1}); s.insert({r + 1, v});
                if (last[u]) last[r + 1] = last[u] + (r - u + 1);
            }
        }
        timer += (r - l + 1);
    }

    for (int i = 0; i < q; ++ i){
        ll s; cin >> s;
        e.emplace_back(s, i);
    }

    vector <long long> ans(q);
    sort(e.begin(), e.end());
    reverse(e.begin(), e.end());
    long long cur = 0;
    for (auto [d, id] : e){
        if (id > q) cur += id - q;
        else ans[id] = cur;
    }
    for (long long &f : ans) cout << f << ' ';
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
Main.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
Main.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
Main.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
Main.cpp: In function 'int main()':
Main.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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