Submission #522770

#	Time	Username	Problem	Language	Result	Execution time	Memory
522770		dsyz	Pilot (NOI19_pilot)	C++17	100 / 100	608 ms	99580 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll parent[MAXN];
ll SIZE[MAXN];
long long find_set(ll a){
	if(parent[a] == a) return a;
	parent[a] = find_set(parent[a]);
	return parent[a];
}
bool same_set(ll x,ll y){
	return find_set(x) == find_set(y);
}
void merge_set(ll x,ll y){
	parent[find_set(x)] = find_set(y);
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q;
	cin>>N>>Q;
	ll sum = 0;
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];		
	}
	pair<ll,ll> planes[Q];
	for(ll i = 0;i < Q;i++){
		cin>>planes[i].first;
		planes[i].second = i;
	}
	ll prefix[N + 1];
	ll cur = 0;
	for(ll i = 0;i <= N;i++){
		cur += i;
		prefix[i] = cur;
	}
	deque<pair<ll,ll> > dq;
	for(ll i = 0;i < N;i++){
		dq.push_back(make_pair(arr[i],i));
	}
	ll ans[Q];
	ll can[N];
	memset(can,0,sizeof(can));
	memset(ans,0,sizeof(ans));
	for(ll i = 0;i < N;i++){
		parent[i] = i;
	}
	for(ll i = 0;i < N;i++){
		SIZE[i] = 1;
	}
	sort(planes,planes + Q);
	sort(dq.begin(),dq.end());
	queue<ll> q;
	for(ll i = 0;i < Q;i++){
		while(dq.size() != 0 && dq.front().first <= planes[i].first){
			ll a = dq.front().first;
			ll index = dq.front().second;
			can[index] = i + 1;
			q.push(index);
			dq.pop_front();
			if(N == 1){
			
			}else if(index == 0){
				ll b = 0;
				ll c = 0;
				if(can[index + 1] >= 1){
					b = find_set(index + 1);
					sum -= prefix[SIZE[b]];
					c += SIZE[b];
					merge_set(index,index + 1);
					b = find_set(index + 1);
					SIZE[b] = c + 1;
					sum += prefix[SIZE[b]];					
				}else{
					sum++;
				}
			}else if(index == N - 1){
				ll b = 0;
				ll c = 0;
				if(can[index - 1] >= 1){
					b = find_set(index - 1);
					sum -= prefix[SIZE[b]];
					c += SIZE[b];
					merge_set(index,index - 1);
					b = find_set(index - 1);
					SIZE[b] = c + 1;
					sum += prefix[SIZE[b]];					
				}else{
					sum++;
				}	
			}else{
				ll b = 0;
				ll c = 0;
				if(can[index - 1] >= 1){
					b = find_set(index - 1);
					sum -= prefix[SIZE[b]];
					c += SIZE[b];				
				}
				if(can[index + 1] >= 1){
					b = find_set(index + 1);
					sum -= prefix[SIZE[b]];
					c += SIZE[b];					
				}
				if(can[index - 1] >= 1) merge_set(index,index - 1);
				if(can[index + 1] >= 1) merge_set(index,index + 1);
				b = find_set(index);
				SIZE[b] = c + 1;
				sum += prefix[SIZE[b]];
			}			
		}
		ans[planes[i].second] = sum;
	}
	for(ll i = 0;i < Q;i++){
		cout<<ans[i]<<'\n';
	}
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:57:7: warning: unused variable 'a' [-Wunused-variable]
   57 |    ll a = dq.front().first;
      |       ^

• 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