제출 #956725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956725		MilosMilutinovic	Pilot (NOI19_pilot)	C++14	100 / 100	386 ms	56608 KiB

pilot

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll 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;
}

int n,q;
int a[1000005],sz[1000005],fa[1000005];
vector<pii> qry;
ll res[1000005],cur;

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

int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}

void unite(int x,int y){
	x=getf(x);
	y=getf(y);
	if(x==y) return;
	cur-=f(sz[x]);
	cur-=f(sz[y]);
	sz[x]+=sz[y];
	cur+=f(sz[x]);
	fa[y]=x;
}
int main(){
	n=readint(); q=readint();
	int x;
	for(int i=1;i<=n;i++){
		x=readint();
		qry.pb(mp(x,-i));
	}
	for(int i=1;i<=q;i++){
		x=readint();
		qry.pb(mp(x,i));
	}
	sort(qry.begin(),qry.end());
	for(auto p:qry){
		int idx=p.se;
		if(idx<0){
			idx=-idx;
			sz[idx]=1;
			fa[idx]=idx;
			cur+=1;
			if(a[idx-1]==1) unite(idx,idx-1);
			if(a[idx+1]==1) unite(idx,idx+1);
			a[idx]=1;
		}else{
			res[idx]=cur;
		}
	}
	for(int i=1;i<=q;i++) printf("%lld\n",res[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