Submission #36061

#	Time	Username	Problem	Language	Result	Execution time	Memory
36061		UncleGrandpa925	Money (IZhO17_money)	C++14	100 / 100	296 ms	9828 KiB

money

/*input
4
4 6 1 7
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define N 1000005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n;
int a[N];
int tree[N];

void update(int i, int val) {
	for (; i; i -= i & -i) tree[i] = min(tree[i], val);
}

int get(int i) {
	int ret = 1e9;
	for (; i <= N - 5; i += i & -i) {
		ret = min(ret, tree[i]);
	}
	return ret;
}

signed main() {
	memset(tree, 127, sizeof(tree));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int t; scanf("%d", &a[i]);
	}
	int last = a[0], ans = 0;
	int mx = 1e9;
	update(a[0] - 1, a[0]);
	int len = 1;
	for (int i = 1; i < n; i++) {
		if (a[i] < last) {
			ans++;
			mx = get(a[i]);
		}
		else if (a[i] > mx) {
			ans++;
			mx = get(a[i]);
		}
		last = a[i];
		update(a[i] - 1, a[i]);
	}
	ans++;
	printf("%d\n", ans);
}

Compilation message (stderr)

money.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
money.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
money.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<int, int> >&)':
money.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
money.cpp: In function 'int main()':
money.cpp:48:7: warning: unused variable 't' [-Wunused-variable]
   int t; scanf("%d", &a[i]);
       ^
money.cpp:53:6: warning: unused variable 'len' [-Wunused-variable]
  int len = 1;
      ^
money.cpp:46:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
money.cpp:48:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &a[i]);
                            ^

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