Submission #640442

#	Time	Username	Problem	Language	Result	Execution time	Memory
640442		kgh3620	Untitled (POI11_tem)	C++17	0 / 100	1059 ms	57148 KiB

Main

#pragma GCC optimize("O3") 
#pragma GCC optimize("Ofast")

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

int n;
int x[1000000];
int y[1000000];
map <int,int> dp;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n;

	for(int i=0;i<n;i++)
	{
		cin >> x[i] >> y[i];
	}

	deque <pair<int,int> > dque;
	int res = 1;
	dp[x[0]] = 1;
	dque.push_back(make_pair(dp[x[0]],x[0]));
	for(int i=1;i<n;i++)
	{
		if(!dque.empty())
		{
			int a = dque.front().second;
			if(a <= y[i])
			{
				int b = max(a,x[i]);
				if(dp.find(b)==dp.end())
				{
					dp[b] = dque.front().first + 1;
				}
				else
				{
					dp[b] = max(dp[b],dque.front().first + 1);
				}
				while(!dque.empty())
				{
					if(dque.back().first < dp[b])
					{
						dque.pop_back();
						continue;
					}
					else if(dque.back().first == dp[b])
					{
						if(dque.back().second > b)
						{
							dque.pop_back();
							continue;
						}
						else
						{
							break;
						}
					}
					break;
				}
				dque.push_back(make_pair(dp[b],b));
				res = max(res,dp[b]);
			}
			else
			{
				if(dp.find(x[i])==dp.end())
				{
					dp[x[i]] = 1;
				}
				else
				{
					dp[x[i]] = max(dp[x[i]],1);
				}
				while(!dque.empty())
				{
					if(dque.back().first < dp[x[i]])
					{
						dque.pop_back();
						continue;
					}
					else if(dque.back().first == dp[x[i]])
					{
						if(dque.back().second > x[i])
						{
							dque.pop_back();
							continue;
						}
						else
						{
							break;
						}
					}
					break;
				}
				dque.push_back(make_pair(dp[x[i]],x[i]));			
				res = max(res,dp[x[i]]);	
			}
		}
		else
		{
			if(dp.find(x[i])==dp.end())
			{
				dp[x[i]] = 1;
			}
			else
			{
				dp[x[i]] = max(dp[x[i]],1);
			}
			while(!dque.empty())
			{
				if(dque.back().first < dp[x[i]])
				{
					dque.pop_back();
					continue;
				}
				else if(dque.back().first == dp[x[i]])
				{
					if(dque.back().second > x[i])
					{
						dque.pop_back();
						continue;
					}
					else
					{
						break;
					}
				}
				break;
			}
			dque.push_back(make_pair(dp[x[i]],x[i]));				
			res = max(res,dp[x[i]]);
		}
	}

	cout << res << '\n';

	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9