oj.uz

Submission #901890

# Submission time Handle Problem Language Result Execution time Memory
901890 2024-01-10T03:10:59 Z ForgottenDestiny Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> seg;

void build() {
    for(int i=n-1;i>0;i--) seg[i]=max(seg[i<<1],seg[i<<1|1]);
}


void modify(int p, int value) {
    for(seg[p+=n]=value;p>1;p>>=1) seg[p>>1]=max(seg[p],seg[p^1]); 
}

int query(int l, int r){ // remember, this works over range [l,r)
    int res=-1;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
        if(l&1) res=max(res,seg[l++]); //remember, this needs to be l++, ++l will WA
        if(r&1) res=max(res,seg[--r]); 
    }
    return res;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin>>n>>m;
    vector<pair<int,int>> pics(n);
    seg.resize(2*n);
    vector<int> frames(m);
    for (int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        pics[i]={a,b};
    }
    sort(pics.begin(),pics.end());
    for(int i=0;i<m;i++){
        cin>>frames[i];
    }
    sort(frames.begin(),frames.end());
    set<pair<int,int>> values;
    for (int i=0;i<n;i++){
        values.insert({pics[i].second,i});
    }
    for (int i=0;i<n;i++){
        seg[n+i]=pics[i].second;
    }
    build();
    int res=0;
    for(int i=m-1;i>=0;i--){
        auto it=upper_bound(pics.begin(),pics.end(),make_pair(frames[i],(int)1e9+1));
        if(it==pics.begin()){
            break;
        }
        int r=it-pics.begin();
        // cerr<<r<<"\n";
        int k = query(0,r);
        // cerr<<k<<"\n";
        if(k==-1){
            break;
        }
        res++;
        auto it2=upper_bound(values.begin(),values.end(),make_pair(k,n+1));
        it2--;
        int sec=(*it2).second;
        modify(sec,-1);
        values.erase(it2);

    }
    cout<<res<<"\n";

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -