Submission #369274

#	Time	Username	Problem	Language	Result	Execution time	Memory
369274		Berted	Pilot (NOI19_pilot)	C++11	100 / 100	669 ms	42080 KiB

pilot

#include <iostream>
#include <algorithm>
#define pii pair<int,int>
#define fst first
#define snd second
#define ll long long
using namespace std;
int n,q;pii ar[1000001]={},qry[1000001]={};
int prt[1000001]={},sz[1000001]={};
ll to = 0,rs[1000001]={};
int fn(int x) {return prt[x] = (prt[x] - x)?fn(prt[x]):x;}
void jn(int a,int b)
{
	a = fn(a), b = fn(b);
	if (a!=b)
	{
		if (sz[a]<sz[b]) {swap(a,b);}
		prt[b] = a;
		to -= (ll)sz[b]*(sz[b]+1)/2;
		to -= (ll)sz[a]*(sz[a]+1)/2;
		sz[a] += sz[b];sz[b] = 0;
		to += (ll)sz[a]*(sz[a]+1)/2;
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for (int i=0;i<n;i++) {cin>>ar[i].fst;ar[i].snd = i;prt[i] = -1;}
	for (int i=0;i<q;i++) {cin>>qry[i].fst;qry[i].snd = i;}
	sort(ar,ar+n);sort(qry,qry+q);
	int j = 0;
	for (int i=0;i<q;i++)
	{
		for (;j<n;j++)
		{
			if (ar[j].fst<=qry[i].fst) 
			{
				prt[ar[j].snd] = ar[j].snd;
				sz[ar[j].snd] = 1;to++;
				if (ar[j].snd)
				{
					if (prt[ar[j].snd-1]!=-1)
					{
						jn(ar[j].snd,ar[j].snd-1);
					}
				}
				if (ar[j].snd<n-1)
				{
					if (prt[ar[j].snd+1]!=-1)
					{
						jn(ar[j].snd,ar[j].snd+1);
					}
				}
			}
			else {break;}
		}
		rs[qry[i].snd] = to;
	}
	for (int i=0;i<q;i++)
	{
		cout<<rs[i]<<"\n";
	}
	return 0;
}

• 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