Submission #676484

#	Time	Username	Problem	Language	Result	Execution time	Memory
676484		penguin133	Pilot (NOI19_pilot)	C++17	100 / 100	933 ms	59720 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
int parent[1000005];
long long root[1000005];
pair<int, int> arr[1000005];
pair<int, long long> s[1000005];
int exis[1000005];
int getr(int p){
	if(parent[p] == p)return p;
	else return parent[p] = getr(parent[p]);
}
void merge(int a,int b){
	a = getr(a);b=getr(b);
	if(a != b){
		root[a]  += root[b];
		parent[b] = parent[a];
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		parent[i]= i;
		root[i] = 1;
	}
	for(int i=1;i<=n;i++){
		cin >> arr[i].first;
		arr[i].second = i;
		s[i].first = arr[i].first;
	}
	sort(arr+1, arr + n+1);
	sort(s+1, s + n+1);
	long long ans = 0;
	for(int i=1;i<=n;i++){
		int cur = arr[i].second;
		exis[cur] = true;
		
		if(exis[cur-1] == true && exis[cur+1] == true){
			ans -= (root[getr(cur-1)] * (root[getr(cur-1)]+1))/2;
			ans -= (root[getr(cur+1)] * (root[getr(cur+1)] + 1))/2;
			merge(cur-1, cur);
			merge(cur, cur+1);
			ans += root[getr(cur-1)] * (root[getr(cur-1)] +1 )/2;
		}
		else{
			if(exis[cur-1] == true){
				ans -= root[getr(cur-1)] * (root[getr(cur-1)] + 1)/2;
				merge(cur-1, cur);
				ans += root[getr(cur-1)] * (root[getr(cur-1)]+1)/2;
			}
			else if(exis[cur+1] == true){
				ans -= root[getr(cur+1)] * (root[getr(cur+1)] + 1)/2;
				merge(cur, cur+1);
				ans += root[getr(cur)]*(root[getr(cur)] + 1)/2;
			}
			else{
				ans++;
			}
		}
		
		if(i == n || arr[i].first != arr[i+1].first){
			s[i].second = ans;
		}
	}
	for(int i=0;i<q;i++){
		int a;
		cin >> a;
		int start = 1, end = n;
		int index = -1;
		while(start <= end){
			int m = (start+end)/2;
			if(s[m].first <= a){
				index = max(index, m);
				start = m + 1;
			}
			else{
				end = m -1;
			}
		}
		cout << s[index].second << "\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