Submission #1266361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266361		PlayVoltz	Pilot (NOI19_pilot)	C++20	100 / 100	295 ms	38872 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair

const int MAXN=1e6+5;

int ans[MAXN], s[MAXN];

void merge(int val, int i){
	if (!s[i]||!s[i+1])return;
	int l=i-s[i]+1, r=i+s[i+1];
	ans[val]+=s[l]*s[r];
	s[l]=s[r]=r-l+1;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q, a;
	cin>>n>>q;
	vector <pii> vect(n+1);
	for (int i=1; i<=n; ++i){
		cin>>vect[i].first;
		vect[i].second=i;
	}
	sort(vect.begin(), vect.end());
	for (int i=1, j=1; i<=1e6; ++i){
		ans[i]=ans[i-1];
		for (;vect[j].first==i; ++j){
			s[vect[j].second]=1;
			++ans[i];
			merge(i, vect[j].second-1);
			merge(i, vect[j].second);
		}
	}
	while (q--){
		cin>>a;
		cout<<ans[a]<<"\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