Submission #1096496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096496		Trisanu_Das	Pilot (NOI19_pilot)	C++17	100 / 100	215 ms	36684 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int dp[1010101], h[1010101], S[1010101], n, q, i, j;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	h[0] = 1000005;
	cin >> n >> q;
	for(i = 1, j = 0; i <= n; i++){
		cin >> h[i];
		for(; j && h[S[j]] < h[i]; j --) dp[h[S[j]]] += (i - S[j]) * (S[j] - S[j - 1]);
		S[++j] = i;
	}
	for(; j; j--) dp[h[S[j]]] += (i - S[j]) * (S[j] - S[j - 1]);
	for(i = 1; i <= 1e6; i++) dp[i] += dp[i - 1];
	while(q--){
		int y; cin >> y;
		cout << dp[y] << '\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