Submission #217741

#	Time	Username	Problem	Language	Result	Execution time	Memory
217741		quocnguyen1012	Pilot (NOI19_pilot)	C++14	100 / 100	489 ms	40580 KiB

pilot

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int N, Q, h[maxn];ll res[maxn];
int nl[maxn], nr[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q;
  for(int i = 1; i <= N; ++i)
    cin >> h[i];
  vector<int> st;
  for(int i = 1; i <= N; ++i){
    while(st.size() && h[st.back()] < h[i]) st.pop_back();
    if(st.empty()) nl[i] = 0;
    else nl[i] = st.back();
    st.eb(i);
  }
  st.clear();
  for(int i = N; i >= 1; --i){
    while(st.size() && h[st.back()] <= h[i]) st.pop_back();
    if(st.empty()) nr[i] = N + 1;
    else nr[i] = st.back();
    st.eb(i);
  }
  for(int i = 1; i <= N; ++i){
    res[h[i]] += 1ll * (i - nl[i]) * (nr[i] - i);
  }
  for(int i = 1; i < maxn; ++i)
    res[i] += res[i - 1];
  while(Q--){
    int x; cin >> x;
    cout << res[x] << '\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