Submission #1162564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162564		abysmal	Exhibition (JOI19_ho_t2)	C++20	0 / 100	0 ms	324 KiB

joi2019_ho_t2

#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stdint.h>
#include<vector>

#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...)
#endif

using namespace std;

const int64_t INF = (int64_t) 1e18 + 777;
const int64_t mINF = (int64_t) 1e9 + 777;
const int64_t MOD = (int64_t) 1e9 + 7;

struct Picture
{
    int s; int v;

    Picture(int s_, int v_) : s(s_), v(v_) {}

    bool operator < (const Picture& o) 
    {
        return v < o.v;
    }
};

struct Solution
{
    vector<int> bit;
	Solution() {}

	void solve()
	{
        int n; int m;
        cin >> n >> m;
        vector<Picture> pic;
        vector<int> c(m);
        for(int i = 0; i < n; i++)
        {
            int s; int v;
            cin >> s >> v;

            pic.emplace_back(s, v);
        }

        for(int i = 0; i < m; i++)
        {
            cin >> c[i];
        }

        bit.resize(m + 1, 0);
        vector<bool> taken(m, false);
        sort(c.begin(), c.end());
        sort(pic.begin(), pic.end());
        int ans = 0; 
        for(int i = 0; i < n; i++)
        {
            int s = pic[i].s;

            int l = 0; int r = m - 1;
            int x = -1;
            while(l <= r)
            {
                int mid = l + (r - l) / 2;

                if(c[mid] >= s)
                {
                    x = mid;
                    if(taken[mid]) l = mid + 1;
                    else r = mid - 1;
                }
                else l = mid + 1;
            }

            if(x == -1) continue;
            taken[x] = true;
            int dp = get(x);
            ans = max(ans, dp + 1);
            update(x + 1, dp + 1);
        }

        cout << ans << "\n";
	}

    int get(int i)
    {
        int res = 0;
        while(i > 0)
        {
            res = max(res, bit[i]);

            i -= i & (-i);
        }
        return res;
    }

    void update(int i, int val)
    {
        while(i < (int) bit.size())
        {
            bit[i] = max(bit[i], val);

            i += i & (-i);
        }
    }

	int modadd(int a, int b)
	{
		int res = a + b;
		if(res >= MOD) res -= MOD;
		return res;
	}

	int modmul(int a, int b)
	{
		return (1LL * a * b) % MOD;
	}
};

int main()
{
	int t = 1;
	//cin >> t;
	for(int i = 0; i < t; i++)
	{
		Solution().solve();
	}
	return 0;
}

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