Submission #230744

#	Time	Username	Problem	Language	Result	Execution time	Memory
230744		pavement	Baloni (COCI15_baloni)	C++17	100 / 100	118 ms	38904 KiB

baloni

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef TEST
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define ins insert
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, T, link[1000005], sz[1000005];
vector<int> H[1000005];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

bool unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return 0;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
	return 1;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	T = N;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 1, tmp; i <= N; i++) {
		cin >> tmp;
		if (H[tmp + 1].size()) {
			T -= unite(i, H[tmp + 1].back());
			H[tmp + 1].ppb();
		}
		H[tmp].pb(i);
	}
	cout << T << '\n';
}

Compilation message (stderr)

baloni.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 100 / 100