Submission #1170522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170522		zrzzrz	Pilot (NOI19_pilot)	C++20	100 / 100	382 ms	42672 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
int n,q,h[1000005],Fa[1000005],siz[1000005];
long long ans,Ans[1000005];
struct Node{
	int x,id;
	bool operator<(const Node &T)const{
		return x<T.x;
	}
}a[1000005],b[1000005];
int GetFa(int x){
	return x==Fa[x]?x:Fa[x]=GetFa(Fa[x]);
}
long long calc(int x){
	return 1ll*x*(x-1)/2;
}
void Merge(int u,int v){
	if (u<1||u>n||h[u]>h[v]) return;
	int x=GetFa(u),y=GetFa(v);
	if (x==y) return;
	ans-=calc(siz[x])+calc(siz[y]);
	Fa[x]=y,siz[y]+=siz[x];
	ans+=calc(siz[y]);
} 
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) scanf("%d",&a[i].x),h[i]=a[i].x,a[i].id=Fa[i]=i,siz[i]=1;
	for (int i=1;i<=q;i++) scanf("%d",&b[i].x),b[i].id=i;
	sort(a+1,a+n+1),sort(b+1,b+q+1);
	int p=1;
	for (int i=1;i<=n;i++){
		while (p<=q&&b[p].x<a[i].x) Ans[b[p].id]=ans+i-1,p++;
		Merge(a[i].id-1,a[i].id);
		Merge(a[i].id+1,a[i].id);
	}
	while (p<=q) Ans[b[p].id]=ans+n,p++;
	for (int i=1;i<=q;i++) printf("%lld\n",Ans[i]);
	return 0; 
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d%d",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~
pilot.cpp:27:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         for (int i=1;i<=n;i++) scanf("%d",&a[i].x),h[i]=a[i].x,a[i].id=Fa[i]=i,siz[i]=1;
      |                                ~~~~~^~~~~~~~~~~~~~
pilot.cpp:28:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         for (int i=1;i<=q;i++) scanf("%d",&b[i].x),b[i].id=i;
      |                                ~~~~~^~~~~~~~~~~~~~

• 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