제출 #1291070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291070		kubinsgk8	Exhibition (JOI19_ho_t2)	C++20	0 / 100	15 ms	31868 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;

//_______________________________________________

const int  N=1e5+2;

struct bg
{
    long long val, sz, idx;
};

long long n, m;

bg a[N];

long long b[N];




//_______________________________________________


bool cmp1(bg x, bg y)
{
    return x.val<y.val;
}

bool cmp2(bg x, bg y)
{
    return x.sz<y.sz;
}


namespace sub2
{

    bool check()
    {
        return (n<=1000 and m<=1000);
    }

    long long node[1002][4*1002];




    void update(int vitri, int goc, int l, int r, int idx, long long value)
    {
        if(idx<l or idx>r)return ;

        if(l==r)
        {
            node[vitri][goc]=max(node[vitri][goc], value);
            return;
        }

        int mid=(l+r)>>1;

        update(vitri, goc*2, l, mid, idx, value);

        update(vitri, goc*2+1, mid+1, r, idx, value);

        node[vitri][goc]=max(node[vitri][goc*2], node[vitri][goc*2+1]);

    }

    long long get(int vitri, int goc, int l, int r, int trai, int phai)
    {
        if(trai>phai)return 0;

        if(l>phai or r<trai)return 0;

        if(trai<=l and r<=phai)return node[vitri][goc];


        int mid=(l+r)>>1;


        return max(get(vitri, goc*2, l, mid, trai, phai), get(vitri, goc*2+1, mid+1, r, trai, phai));
    }





    void solve()
    {
        memset(node, 0, sizeof node);

        long long ans=0;

        for(int i=1; i<=n; i++)
        {


            for(int j=1; j<=m; j++)
            {

                if(a[i].sz<=b[j])
                {
                    long long temp=0;

                    if(a[i].idx>1)
                     temp=get(j-1, 1,  1, n, 1, a[i].idx-1);


                    update(j, 1, 1, n, a[i].idx, temp+1);

                    ans=max(ans, temp+1);
                }

            }


        }


        cout<<ans;

    }

}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;

    for(int i=1; i<=n; i++)
    {
        cin>>a[i].sz>>a[i].val;
    }

    for(int i=1; i<=m; i++)cin>>b[i];

    sort(b+1, b+m+1);

    sort(a+1, a+n+1, cmp1);

    for(int i=1; i<=n; i++)a[i].idx=i;

    sort(a+1, a+n+1, cmp2);


    if(sub2::check())sub2::solve();




    return 0;
}

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