Submission #223604

#	Time	Username	Problem	Language	Result	Execution time	Memory
223604		blackbori	Pilot (NOI19_pilot)	C++14	100 / 100	472 ms	33096 KiB

pilot

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll D[1010101];
int A[1010101], S[1010101];
int n;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int q, i, j, t;

	cin >> n >> q;

	for(i = 1, j = 0, A[0] = 1e6 + 1; i <= n; i ++){
		cin >> A[i];
		for(; j && A[S[j]] < A[i]; j --){
			D[A[S[j]]] += (ll)(i - S[j]) * (S[j] - S[j - 1]);
		}
		S[++ j] = i;
	}

	for(; j; j --){
		D[A[S[j]]] += (ll)(i - S[j]) * (S[j] - S[j - 1]);
	}

	for(i = 1; i <= 1e6; i ++){
		D[i] += D[i - 1];
	}

	for(; q --; ){
		cin >> t;
		cout << D[t] << "\n";
	}

	return 0;
}

• 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