Submission #1014541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014541		ttttttttttttth	Pilot (NOI19_pilot)	C++17	100 / 100	229 ms	52324 KiB

pilot

// Author: Ivan Teo 
// Created: Fri Jul  5 12:08:34 2024

#define TASKNAME "636085S" 
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=========================================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}
template<int D, typename T> struct Vec : public vector<Vec<D - 1, T>> { template<typename... Args> Vec(int n = 0, Args... args) : vector < Vec < D - 1, T >> (n, Vec < D - 1, T > (args...)) {} };
template<typename T> struct Vec<1, T> : public vector<T> { Vec(int n = 0, const T &val = T()) : vector<T>(n, val) {} };

void solve()
{
    int n, q;
    cin >> n >> q;
    vi a(n + 1);
    fore(i, 1, n) cin >> a[i];
    stack<int> st;
    vi l(n + 1), r(n + 1);
    fore(i, 1, n)
    {
        while (sz(st) && a[i] >= a[st.top()]) st.pop();
        l[i] = st.empty() ? 1 : (st.top() + 1);
        st.push(i);
    }
    st = stack<int>();
    for (int i = n; i >= 1; i--)
    {
        while (sz(st) && a[i] > a[st.top()]) st.pop();
        r[i] = st.empty() ? n : (st.top() - 1);
        st.push(i);
    }
    vi ans(1e6 + 1);
    fore(i, 1, n)
        ans[a[i]] += (i - l[i] + 1) * (r[i] - i + 1);
    fore(i, 1, 1e6) ans[i] += ans[i - 1];
    while (q--)
    {
        int x; cin >> x;
        cout << ans[x] << '\n';
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(TASKNAME ".inp", "r"))
    {
        freopen(TASKNAME ".inp", "r", stdin);
        freopen(TASKNAME ".out", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el;
    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(TASKNAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(TASKNAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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