Submission #230744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
230744	2020-05-11T14:11:07 Z	pavement	Baloni (COCI15_baloni)	C++17	100 / 100	118 ms	38904 KB

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

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23936 KB	Output is correct
2	Correct	18 ms	23936 KB	Output is correct
3	Correct	19 ms	23936 KB	Output is correct
4	Correct	19 ms	24064 KB	Output is correct
5	Correct	110 ms	37500 KB	Output is correct
6	Correct	118 ms	38904 KB	Output is correct
7	Correct	96 ms	36344 KB	Output is correct
8	Correct	97 ms	36216 KB	Output is correct
9	Correct	108 ms	36856 KB	Output is correct
10	Correct	107 ms	37524 KB	Output is correct