Submission #361814

#	Time	Username	Problem	Language	Result	Execution time	Memory
361814		Lawliet	Money (IZhO17_money)	C++17	100 / 100	1334 ms	51408 KiB

money

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

const int MAXN = 1000010;
const int INF = 1000000010;

int n;

int v[MAXN];

set<int> s;

void add(int L, int R)
{
	while( L <= R )
		s.insert( v[L++] );
}

void solveTestCase()
{
	scanf("%d",&n);

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

	int Lord = 1;
	int ans = 1, opt = 1;

	int Lvalue = v[1], Rvalue = INF;

	for(int i = 2 ; i <= n ; i++)
	{
		if( v[i - 1] > v[i] )
		{
			add( Lord , i - 1 );
			Lord = i;
		}

		if( Lord == 1 ) continue;
		if( Lord != i && v[i] <= Rvalue ) continue;

		// opt = i;
		// add( opt , i - 1 );		

		ans++;

		auto it = s.upper_bound( v[i] );

		if( it == s.end() ) Rvalue = INF;
		else Rvalue = *it;

		if( it == s.begin() ) Lvalue = -INF;
		else it--, Lvalue = *it;
	}

	printf("%d\n",ans);
}

int main()
{
	int t = 1;
	// scanf("%d",&t);

	while( t-- )
		solveTestCase();
}

Compilation message (stderr)

money.cpp: In function 'void solveTestCase()':
money.cpp:30:15: warning: unused variable 'opt' [-Wunused-variable]
   30 |  int ans = 1, opt = 1;
      |               ^~~
money.cpp:32:6: warning: variable 'Lvalue' set but not used [-Wunused-but-set-variable]
   32 |  int Lvalue = v[1], Rvalue = INF;
      |      ^~~~~~
money.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
money.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   scanf("%d",&v[i]);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55