oj.uz

Submission #640442

# Submission time Handle Problem Language Result Execution time Memory
640442 2022-09-14T16:25:13 Z kgh3620 Temperature (POI11_tem) C++17
0 / 100
 1000 ms 57148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 6912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 42208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 53884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 57148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 588 ms 35956 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 11992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 11340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 54468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 52356 KB Time limit exceeded
2 Halted 0 ms 0 KB -