oj.uz

답안 #901905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901905 2024-01-10T03:30:52 Z ForgottenDestiny Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 344 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());
    vector<tuple<int,int,int>> values;
    for (int i=0;i<n;i++){
        values[i]={pics[i].second,pics[i].first,i};
    }
    for (int i=0;i<n;i++){
        seg[n+i]=pics[i].second;
    }
    build();
    int res=0;
    //O(n+nlogn+m+mlogm+nlogn)
    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++;
        tuple<int,int,int> cur={k,frames[i],n+1};
        auto it2=upper_bound(values.begin(),values.end(),cur);
        it2--;
        int sec=get<2>(*it2);
        modify(sec,-1);
        values.erase(it2);
    }
    cout<<res<<"\n";

    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -