Submission #305804

#	Time	Username	Problem	Language	Result	Execution time	Memory
305804		T0p_	Exhibition (JOI19_ho_t2)	C++14	0 / 100	1 ms	384 KiB

joi2019_ho_t2

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

struct picture
{
	int s, v;
	bool operator < (const picture & o) const
	{
		return v < o.v;	
	}
};

picture p[100100];
int f[100100], dp[100100];
stack<int> stk, tmp;

int main()
{
	int n, m;
	scanf(" %d %d",&n,&m);
	for(int i=1 ; i<=n ; i++)
		scanf(" %d %d",&p[i].s,&p[i].v);
	for(int i=1 ; i<=m ; i++)
		scanf(" %d",&f[i]);
	sort(p+1, p+n+1);
	sort(f+1, f+m+1);
	stk.push(0);
	for(int i=1 ; i<=n ; i++)
	{	
		int l = 1, r = m+1;
		while(l != r)
		{
			int mid = (l+r)>>1;
			(p[i].s <= f[mid]) ? r = mid : l = mid+1;
		}
		if(l == m+1) continue ;
		while(l <= stk.top())
		{
			dp[stk.top() + 1] = max(dp[stk.top()+1], dp[stk.top()] + 1);
			tmp.push(stk.top() + 1);
			stk.pop();
		}
		dp[l] = max(dp[l], dp[stk.top()] + 1);
		stk.push(l);
		while(!tmp.empty())
		{
			stk.push(tmp.top());
			tmp.pop();
		}
	}
	int ans = 0;
	for(int i=1 ; i<=m ; i++)
		ans = max(ans, dp[i]);
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf(" %d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t2.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |   scanf(" %d %d",&p[i].s,&p[i].v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t2.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf(" %d",&f[i]);
      |   ~~~~~^~~~~~~~~~~~~

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