oj.uz

Submission #901898

# Submission time Handle Problem Language Result Execution time Memory
901898 2024-01-10T03:18:55 Z ForgottenDestiny Exhibition (JOI19_ho_t2) C++17
50 / 100
 1000 ms 11484 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<tuple<int,int,int>> values;
    for (int i=0;i<n;i++){
        values.insert({pics[i].second,pics[i].first,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++;
        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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
8 Correct 0 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 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
8 Correct 0 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 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 4 ms 348 KB Output is correct
21 Correct 4 ms 576 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 5 ms 572 KB Output is correct
25 Correct 5 ms 348 KB Output is correct
26 Correct 6 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 508 KB Output is correct
29 Correct 4 ms 464 KB Output is correct
30 Correct 5 ms 344 KB Output is correct
31 Correct 4 ms 568 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 3 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 6 ms 668 KB Output is correct
37 Correct 5 ms 348 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
8 Correct 0 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 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 4 ms 348 KB Output is correct
21 Correct 4 ms 576 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 5 ms 572 KB Output is correct
25 Correct 5 ms 348 KB Output is correct
26 Correct 6 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 508 KB Output is correct
29 Correct 4 ms 464 KB Output is correct
30 Correct 5 ms 344 KB Output is correct
31 Correct 4 ms 568 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 3 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 6 ms 668 KB Output is correct
37 Correct 5 ms 348 KB Output is correct
38 Execution timed out 1050 ms 11484 KB Time limit exceeded
39 Halted 0 ms 0 KB -