oj.uz

Submission #1116709

# Submission time Handle Problem Language Result Execution time Memory
1116709 2024-11-22T08:36:05 Z Warinchai Inspections (NOI23_inspections) C++14
100 / 100
 308 ms 39604 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct range{
    int l,r,val;
    range(int _l=0,int _r=0,int _val=0){
        l=_l,r=_r,val=_val;
    }
    friend bool operator<(range a,range b){
        return a.l<b.l;
    }
};
multiset<range>ms;
vector<pair<int,int>>v;
priority_queue<pair<int,int>>pq;
vector<range>pb;
int lz=0;
int add(range x,range cur){
    if(x.l>cur.r)return 0;
    //cerr<<x.l<<" "<<x.r<<" "<<x.val<<":"<<x.r<<"-"<<cur.l<<"+"<<lz<<"+"<<x.val<<","<<min(x.r,cur.r)-max(x.l,cur.l)+1<<"\n";
    pq.push({x.r-cur.l+lz+x.val,min(x.r,cur.r)-max(x.l,cur.l)+1});
    return 1;
}
int rans[200005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int l,r;cin>>l>>r;
        v.push_back({l,r});
    }
    for(auto [l,r]:v){
        //cerr<<"range:"<<l<<" "<<r<<":\n";
        if(!ms.empty()){
            auto x=ms.lower_bound(range(l));
            if(x!=ms.begin()){
                x=prev(x);
                if(x->r>=l)ms.insert(range(x->l,l-1,x->val+(x->r-l+1))),ms.insert(range(l,x->r,x->val)),ms.erase(x);
            }
            x=ms.upper_bound(range(r));
            if(x!=ms.begin()){
                x=prev(x);
                if(x->r>r)ms.insert(range(x->l,r,x->val+x->r-r)),ms.insert(range(r+1,x->r,x->val)),ms.erase(x);
            }
            x=ms.lower_bound(range(l));
            while(x!=ms.end()&&add(*x,range(l,r))){
                x=next(x);
                ms.erase(prev(x));
            }
        }
        lz+=r-l+1;
        ms.insert(range(l,r,-lz));
    }
    //cerr<<"work\n";
    vector<pair<int,int>>qr;
    for(int i=0;i<q;i++){
        int s;cin>>s;
        qr.push_back({s,i});
    }
    sort(qr.begin(),qr.end(),greater<pair<int,int>>());
    int ans=0;
    for(auto x:qr){
        while(!pq.empty()&&pq.top().first>=x.first){
            //cerr<<pq.top().first<<" "<<pq.top().second<<"\n";
            ans+=pq.top().second,pq.pop();
        }
        //cerr<<"\n";
        rans[x.second]=ans;
    }
    for(int i=0;i<q;i++)cout<<rans[i]<<" ";
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto [l,r]:v){
      |              ^

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 728 KB Output is correct
7 Correct 1 ms 336 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 336 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 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 728 KB Output is correct
7 Correct 1 ms 336 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 336 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 41 ms 8108 KB Output is correct
14 Correct 40 ms 8120 KB Output is correct
15 Correct 40 ms 8104 KB Output is correct
16 Correct 43 ms 8380 KB Output is correct
17 Correct 42 ms 8116 KB Output is correct
18 Correct 43 ms 8140 KB Output is correct
19 Correct 42 ms 8372 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 41 ms 8308 KB Output is correct
4 Correct 49 ms 8920 KB Output is correct
5 Correct 158 ms 27204 KB Output is correct
6 Correct 106 ms 25904 KB Output is correct
7 Correct 112 ms 16848 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 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 728 KB Output is correct
7 Correct 1 ms 336 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 336 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 41 ms 8108 KB Output is correct
14 Correct 40 ms 8120 KB Output is correct
15 Correct 40 ms 8104 KB Output is correct
16 Correct 43 ms 8380 KB Output is correct
17 Correct 42 ms 8116 KB Output is correct
18 Correct 43 ms 8140 KB Output is correct
19 Correct 42 ms 8372 KB Output is correct
20 Correct 46 ms 9396 KB Output is correct
21 Correct 41 ms 8628 KB Output is correct
22 Correct 42 ms 9404 KB Output is correct
23 Correct 42 ms 8632 KB Output is correct
24 Correct 41 ms 8116 KB Output is correct
25 Correct 42 ms 8928 KB Output is correct
26 Correct 44 ms 9396 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 728 KB Output is correct
7 Correct 1 ms 336 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 336 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 41 ms 8108 KB Output is correct
14 Correct 40 ms 8120 KB Output is correct
15 Correct 40 ms 8104 KB Output is correct
16 Correct 43 ms 8380 KB Output is correct
17 Correct 42 ms 8116 KB Output is correct
18 Correct 43 ms 8140 KB Output is correct
19 Correct 42 ms 8372 KB Output is correct
20 Correct 1 ms 504 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 41 ms 8308 KB Output is correct
23 Correct 49 ms 8920 KB Output is correct
24 Correct 158 ms 27204 KB Output is correct
25 Correct 106 ms 25904 KB Output is correct
26 Correct 112 ms 16848 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 592 KB Output is correct
29 Correct 46 ms 9396 KB Output is correct
30 Correct 41 ms 8628 KB Output is correct
31 Correct 42 ms 9404 KB Output is correct
32 Correct 42 ms 8632 KB Output is correct
33 Correct 41 ms 8116 KB Output is correct
34 Correct 42 ms 8928 KB Output is correct
35 Correct 44 ms 9396 KB Output is correct
36 Correct 235 ms 29448 KB Output is correct
37 Correct 236 ms 30000 KB Output is correct
38 Correct 153 ms 29136 KB Output is correct
39 Correct 180 ms 26692 KB Output is correct
40 Correct 255 ms 28764 KB Output is correct
41 Correct 254 ms 33924 KB Output is correct
42 Correct 222 ms 34220 KB Output is correct
43 Correct 308 ms 39488 KB Output is correct
44 Correct 284 ms 39604 KB Output is correct
45 Correct 274 ms 28724 KB Output is correct
46 Correct 298 ms 28640 KB Output is correct
47 Correct 237 ms 29256 KB Output is correct
48 Correct 236 ms 29904 KB Output is correct