oj.uz

Submission #1102765

# Submission time Handle Problem Language Result Execution time Memory
1102765 2024-10-18T19:16:12 Z ttamx Inspections (NOI23_inspections) C++17
100 / 100
 280 ms 38232 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int> l(m),r(m);
    vector<int> cnt(n+2);
    for(int i=0;i<m;i++){
        cin >> l[i] >> r[i];
        cnt[l[i]]++;
        cnt[r[i]+1]--;
    }
    vector<pair<ll,int>> qrs;
    vector<ll> ans(q);
    for(int i=0;i<q;i++){
        ll s;
        cin >> s;
        qrs.emplace_back(s,i);
    }
    sort(qrs.rbegin(),qrs.rend());
    vector<pair<ll,int>> a;
    map<int,pair<int,ll>> mp;
    mp[1]={n,-1e18};
    ll t=0;
    ll base=0;
    for(int i=1;i<=n;i++){
        cnt[i]+=cnt[i-1];
        base+=max(0,cnt[i]-1);
    }
    for(int i=0;i<m;i++){
        auto it=prev(mp.upper_bound(l[i]));
        if(it->first<l[i]){
            mp[l[i]]=it->second;
            mp[l[i]].second+=l[i]-it->first;
            it->second.first=l[i]-1;
            it++;
        }
        for(;it!=mp.end()&&it->first<=r[i];it=mp.erase(it)){
            int cl=it->first;
            int cr=min(r[i],it->second.first);
            ll pt=it->second.second;
            int sz=cr-cl+1;
            a.emplace_back(t+cl-l[i]-pt,sz);
            if(cr<it->second.first){
                mp[cr+1]=it->second;
                mp[cr+1].second+=sz;
            }
        }
        mp[l[i]]={r[i],t};
        t+=r[i]-l[i]+1;
    }
    a.emplace_back(1e18,0);
    sort(a.begin(),a.end());
    for(auto [x,y]:a){
        while(!qrs.empty()&&qrs.back().first<x){
            ans[qrs.back().second]=base;
            qrs.pop_back();
        }
        base-=y;
    }
    for(auto x:ans){
        cout << x << " ";
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 396 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 396 KB Output is correct
13 Correct 42 ms 8300 KB Output is correct
14 Correct 37 ms 8332 KB Output is correct
15 Correct 42 ms 9412 KB Output is correct
16 Correct 41 ms 8132 KB Output is correct
17 Correct 42 ms 8900 KB Output is correct
18 Correct 38 ms 8132 KB Output is correct
19 Correct 40 ms 8644 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 44 ms 9412 KB Output is correct
4 Correct 47 ms 9836 KB Output is correct
5 Correct 111 ms 21056 KB Output is correct
6 Correct 109 ms 20544 KB Output is correct
7 Correct 87 ms 17664 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 396 KB Output is correct
13 Correct 42 ms 8300 KB Output is correct
14 Correct 37 ms 8332 KB Output is correct
15 Correct 42 ms 9412 KB Output is correct
16 Correct 41 ms 8132 KB Output is correct
17 Correct 42 ms 8900 KB Output is correct
18 Correct 38 ms 8132 KB Output is correct
19 Correct 40 ms 8644 KB Output is correct
20 Correct 41 ms 9156 KB Output is correct
21 Correct 40 ms 9668 KB Output is correct
22 Correct 46 ms 9144 KB Output is correct
23 Correct 40 ms 9668 KB Output is correct
24 Correct 42 ms 9668 KB Output is correct
25 Correct 43 ms 8900 KB Output is correct
26 Correct 43 ms 9264 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 396 KB Output is correct
13 Correct 42 ms 8300 KB Output is correct
14 Correct 37 ms 8332 KB Output is correct
15 Correct 42 ms 9412 KB Output is correct
16 Correct 41 ms 8132 KB Output is correct
17 Correct 42 ms 8900 KB Output is correct
18 Correct 38 ms 8132 KB Output is correct
19 Correct 40 ms 8644 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 44 ms 9412 KB Output is correct
23 Correct 47 ms 9836 KB Output is correct
24 Correct 111 ms 21056 KB Output is correct
25 Correct 109 ms 20544 KB Output is correct
26 Correct 87 ms 17664 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 41 ms 9156 KB Output is correct
30 Correct 40 ms 9668 KB Output is correct
31 Correct 46 ms 9144 KB Output is correct
32 Correct 40 ms 9668 KB Output is correct
33 Correct 42 ms 9668 KB Output is correct
34 Correct 43 ms 8900 KB Output is correct
35 Correct 43 ms 9264 KB Output is correct
36 Correct 177 ms 27964 KB Output is correct
37 Correct 171 ms 28732 KB Output is correct
38 Correct 172 ms 31544 KB Output is correct
39 Correct 125 ms 25784 KB Output is correct
40 Correct 196 ms 29344 KB Output is correct
41 Correct 253 ms 36072 KB Output is correct
42 Correct 237 ms 38232 KB Output is correct
43 Correct 280 ms 32388 KB Output is correct
44 Correct 274 ms 33204 KB Output is correct
45 Correct 198 ms 30264 KB Output is correct
46 Correct 247 ms 25060 KB Output is correct
47 Correct 255 ms 25788 KB Output is correct
48 Correct 172 ms 30508 KB Output is correct