제출 #1313241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313241		namhh	Pilot (NOI19_pilot)	C++20	100 / 100	400 ms	69676 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+5;
int n,q,ans[N],par[N],sz[N],check[N],res = 0;
pii qr[N],h[N];
void init(){
	for(int i = 1; i <= n; i++) par[i] = i;
}
int find(int u){
	if(u == par[u]) return u;
	return par[u] = find(par[u]);
}
void join(int u, int v){
	u = find(u);
	v = find(v);
	res -= sz[u]*(sz[u]+1)/2;
	res -= sz[v]*(sz[v]+1)/2;
	sz[u] += sz[v];
	par[v] = u;
	res += sz[u]*(sz[u]+1)/2;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
	    cin >> h[i].fi;
	    h[i].se = i;
	}
	for(int i = 1; i <= q; i++){
		cin >> qr[i].fi;
		qr[i].se = i;
	}
	sort(h+1,h+n+1);
	sort(qr+1,qr+q+1);
	init();
	int cur = 1;
	for(int i = 1; i <= q; i++){
		while(cur <= n && h[cur].fi <= qr[i].fi){
			sz[h[cur].se] = 1;
			res++;
			if(h[cur].se > 1 && check[h[cur].se-1]) join(h[cur].se,h[cur].se-1);
			if(h[cur].se < n && check[h[cur].se+1]) join(h[cur].se,h[cur].se+1);
			check[h[cur].se] = 1;
			cur++;
		}
		ans[qr[i].se] = res;
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

• 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