Submission #965496

#	Time	Username	Problem	Language	Result	Execution time	Memory
965496		red24	Pilot (NOI19_pilot)	C++14	100 / 100	645 ms	104532 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define vi vector<int>
#define pi pair<int, int>
#define vpi vector<pi>
#define vvi vector<vi>
#define mp make_pair
#define pb push_back
#define all(x) x.begin()+1, x.end()
const int INF = (int)1e17;

vi parent, siz;
int res = 0;

void make(int x)
{
	parent[x] = x;
	siz[x] = 1;
}

int f(int x)
{
	return ((x)*(x+1))/2ll;
}

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

void unite(int x, int y)
{
	x = find(x); y = find(y);
	if (x == y) return;
	if (siz[x] < siz[y]) swap(x, y);

	res -= f(siz[x]);
	res -= f(siz[y]);

	siz[x] += siz[y];
	parent[y] = x;
	res += f(siz[x]);
}

void solve()
{
	int n, q; cin >> n >> q;
	vi a(n+1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	siz = vi(n+1);
	parent = vi(n+1);

	const int mx = (int)1e6 + 4529;
	vvi idx(mx+100);
	for (int i = 1; i <= n; i++) idx[a[i]].pb(i);

	for (int i = 1; i <= n; i++) make(i);
	vi ans(mx);
	vi vis(n+1);

	for (int el = 1; el <= mx-100; el++)
	{
		for (int i : idx[el])
		{
			res++;
			vis[i] = 1;

			if (i < n && vis[i+1]) unite(i, i+1);
			if (i > 1 && vis[i-1]) unite(i, i-1);
		}
		ans[el] = res;
	}
	while (q--)
	{
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}
 
int32_t main()
{
	auto begin = std::chrono::high_resolution_clock::now();
	// FASTIO
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
 
 
 
	int T = 1;
	//cin >> T;
	for (int i = 1; i <= T; i++)
	{
		//cout << "Case #" << i << ": ";
		solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11