Submission #225664

#	Time	Username	Problem	Language	Result	Execution time	Memory
225664		Fasho	Pilot (NOI19_pilot)	C++14	100 / 100	737 ms	83192 KiB

pilot

#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;

ll n,m,ar[N],sum,t,ans[N],sz[N],dad[N],l=0;

lli p[N],pl[N];

ll find(ll x)
{
	if(dad[x]==x)
		return x;
	return dad[x]=find(dad[x]);
}
void unite(int x,int y)
{
	int dx=find(x);
	int dy=find(y);
	if(dx==dy)
		return;
	sz[dx]+=sz[dy];
	dad[dy]=dx;
}

void f(int x,int z)
{
	if(find(x)==find(z))
		return;
	int y=find(z);
	y=sz[y];
	sum+=sz[find(x)]*y;
	// cout<<x<<sp<<y<<sp<<sz[find(x)]<<sp<<sz[find(y)]<<endl;
	unite(x,z);
}

void add(int ind)
{
	while(p[l+1].fi<=pl[ind].fi && l<n)
	{
		l++;
		int x=p[l].se;
		sum++;
		// cout<<"[d]"<<sp<<ind<<endl;
		if(ar[x-1]<=ar[x] && x-1!=0)
			f(x,x-1);
		if(ar[x+1]<=ar[x] && x+1!=n+1)
			f(x,x+1);
		
	}
}

int main()
{
	fast;
	cin>>n>>m;
	fo(i,1,n)
		dad[i]=i,sz[i]=1;
	fo(i,1,n)
		cin>>p[i].fi,p[i].se=i,ar[i]=p[i].fi;

	// cout<<endl;
	// fo(i,1,n)
	// cout<<ar[i]<<sp;
	// cout<<endl<<endl;


	fo(i,1,m)
		cin>>pl[i].fi,pl[i].se=i;
	sort(p+1,p+n+1);
	sort(pl+1,pl+m+1);

	fo(i,1,m)
	{
		add(i);
		ans[pl[i].se]=sum;
	}
	fo(i,1,m)
		cout<<ans[i]<<endl;



}

• 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