Submission #1170523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170523		kdyl	Pilot (NOI19_pilot)	C++20	100 / 100	352 ms	63056 KiB

pilot

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=1e6+5;
struct Node{
	int w,id;
}a[N],b[N];
int n,q,ans[N],sz[N],sum,fa[N];
bool flag[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool cmp(Node xxx,Node yyy){
	return xxx.w<yyy.w;
}
int g(int x){
	return x*(x+1)/2;
}
signed main(){
	n=read();q=read();
	for(int i=1;i<=n;i++)a[i].w=read(),a[i].id=i,fa[i]=i,sz[i]=1;
	for(int i=1;i<=q;i++)b[i].w=read(),b[i].id=i;
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+q,cmp);
	int l=1;
	for(int i=1;i<=q;i++){
		//cout<<"!!!"<<'\n'; 
		while(l<=n&&a[l].w<=b[i].w){
			int id=a[l].id;
			//cout<<"?"<<id<<'\n';
			if(flag[id-1]){
				sum-=g(sz[find(id-1)]);
				sz[find(id-1)]+=sz[find(id)];
				fa[find(id)]=find(id-1);
			}
			if(flag[id+1]){
				sum-=g(sz[find(id+1)]);
				sz[find(id+1)]+=sz[find(id)];
				fa[find(id)]=find(id+1);
			}
			flag[id]=1;
			sum+=g(sz[find(id)]);
			l++;
		}
		ans[b[i].id]=sum;
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	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