| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1301231 | tryharderforioi100 | Pilot (NOI19_pilot) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t = 1;
//cin >> t;
while(t--)
{
ll n, q;
cin >> n >> q;
ll a[n + 1], i;
vector<pair<ll, ll>>sapxep1;
for(i = 1; i <= n; i++)
{
cin >> a[i];
sapxep1.push_back(make_pair(a[i], i));
}
sort(sapxep1.begin(), sapxep1.end());
ll ans[q + 1];
vector<pair<ll, ll>>sapxep;
for(i = 1; i <= q; i++)
{
ll val;
cin >> val;
sapxep.push_back(make_pair(val, i));
}
sort(sapxep.begin(), sapxep.end());
set<ll>pos;
for(i = 1; i <= n; i++)
{
pos.insert(i);
}
pos.insert(0);
pos.insert(n + 1);
ll ans1 = 0, vtri = 0;
for(i = 0; i < sapxep.size(); i++)
{
while(vtri < sapxep1.size() && sapxep1[vtri].first <= sapxep[i].first)
{
auto it = pos.lower_bound(sapxep1[vtri].second);
auto it1 = it;
auto it2 = it;
it1--;
it2++;
ans1 += max(0LL, (*it2 - *it) * (*it - *it1));
vtri++;
pos.erase(it);
//cout << vtri << " " << ans1 << " " << i << " " << *it << " " << *it1 << " " << *it2 << endl;
}
ans[sapxep[i].second] = ans1;
}
for(i = 1; i <= q; i++)
{
cout << ans[i] << endl;
}
cout << endl;
}
#ifndef ONLINE_JUDGE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
// Author: tryharderforioi100