| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1303590 | yonatanl | Pilot (NOI19_pilot) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1e18;
const ll MAX_SIZE = 2e6;
vll get_amount_of_sails(int N, int Q, vector<int> D, vector<int> Y) {
ll n = N, q = Q;
vll arr(n);
rep(i, 0, n) arr[i] = D[i];
stack<pll> s;
s.push({ -1, INF });
vll l(n);
rep(i, 0, n) {
while (s.top().second <= arr[i]) {
s.pop();
}
l[i] = s.top().first;
s.push({ i, arr[i] });
}
while (!s.empty()) s.pop();
s.push({ n, INF });
vll r(n);
vll smaller(n);
for (ll i = n - 1; i >= 0; i--) {
while (s.top().second < arr[i]) {
s.pop();
}
r[i] = s.top().first;
s.push({ i, arr[i] });
}
vll add(MAX_SIZE);
rep(i, 0, n) {
ll to_add = i - l[i];
ll num_smaller = 0;
add[arr[i]] += to_add * (r[i] - i);
}
vll pref(MAX_SIZE);
pref[0] = 0;
rep(i, 1, add.size()) pref[i] = pref[i - 1] + add[i];
vll res(q);
rep(i, 0, q) {
res[i] = pref[Y[i]];
}
return res;
}