제출 #1148646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148646		dosts	Exhibition (JOI19_ho_t2)	C++20	100 / 100	44 ms	9032 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e5+1,MOD = 998244353,B = 250;
vi val(N);

struct ST {
    vi t;
    void build(int node,int l,int r) {
        if (l == r) {
            t[node]= val[l];
            return;
        }
        int m = (l+r) >> 1;
        build(2*node,l,m),build(2*node+1,m+1,r);
        t[node] = min(t[2*node],t[2*node+1]);
    }
    ST(int nn) {
        t.resize(4*nn+1,0);
        build(1,1,nn);
    }
    int query(int node,int l,int r,int v) {
        if (t[node] > v) return 0;
        if (l == r) return l;
        int m = (l+r) >> 1;
        int q = query(2*node+1,m+1,r,v);
        if (!q) return query(2*node,l,m,v);
        return q;
    }
    int walk(int node,int l,int r,int L,int R,int v) {
        if (l > R || r < L) return 0;
        if (t[node] > v) return 0;
        if (l >= L && r <= R) return query(node,l,r,v);
        int m = (l+r) >> 1;
        int w = walk(2*node+1,m+1,r,L,R,v);
        if (!w) return walk(2*node,l,m,L,R,v);
        return w;
    }
};
void solve() { 
    int n,m;
    cin >> n >> m;
    vi s(n+1),v(n+1);
    for (int i=1;i<=n;i++) cin >> s[i] >> v[i];
    vi frame(m+1);
    for (int i=1;i<=m;i++) cin >> frame[i];
    sort(frame.begin()+1,frame.end());
    vi pics(n+1);
    iota(all(pics),0ll);
    sort(pics.begin()+1,pics.end(),[&](int x,int y) {
        if (v[x] != v[y]) return v[x] < v[y];
        return s[x] < s[y];
    });
    for (int i=1;i<=n;i++) val[i] = s[pics[i]];
    int ans = 0;
    int cur = m,allow = n;
    ST st(n);
    while (cur >= 1 && allow >= 1) {
        int frst = st.walk(1,1,n,1,allow,frame[cur]);
        if (frst == 0) break;
        allow = frst-1;
        ans++;
        cur--;
    }   
    cout << ans << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50