# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123798 | LTTrungCHL | Pilot (NOI19_pilot) | C++20 | 649 ms | 42868 KiB |
///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
//vector <int> lg2;
//void LOG_ARR(int n){
// lg2.resize(n + 3);
// for (int i = 1;i <= n;++i){
// lg2[i] = __lg(i);
// }
//}
const long long oo = 1e9+7;
const int N = 1000003;
int n, q;
int h[N];
pair <int, int> y[N];
int parent[N], sz[N];
long long ans;
long long res[N];
int finds(int u){
if (u == parent[u]) return u;
int pu = finds(parent[u]);
parent[u] = pu;
return pu;
}
long long sum(long long x){
return x * (x + 1)/2;
}
void unions(int u, int v){
u = finds(u);
v = finds(v);
if (u != v){
if (sz[u] < sz[v]) swap(u, v);
ans -= sum(sz[u]);
ans -= sum(sz[v]);
parent[v] = u;
sz[u] += sz[v];
ans += sum(sz[u]);
}
return;
}
void check(int id, int val){
if (id - 1 and h[id - 1] <= val){
unions(id, id - 1);
}
if (id + 1 <= n and h[id + 1] <= val){
unions(id, id + 1);
}
return;
}
void solve(){
cin >> n >> q;
priority_queue <pair <int,int>> pq;
for (int i = 1;i <= n;++i){
cin >> h[i];
parent[i] = i;
sz[i] = 1;
pq.push({-h[i], i});
}
for (int i = 1;i <= q;++i){
cin >> y[i].F;
y[i].S = i;
}
sort(y + 1, y + q + 1);
for (int i = 1;i <= q;++i){
int val = y[i].F;
int idx = y[i].S;
while (!pq.empty() and -pq.top().F <= val){
int id = pq.top().S;
pq.pop();
++ans;
check(id, val);
}
res[idx] = ans;
}
for (int i = 1;i <= q;++i){
cout << res[i] <<"\n";
}
return;
}
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
if (fopen("npt.inp", "r")){
freopen("npt.inp", "r", stdin);
freopen("npt.out", "w", stdout);
}
////////dsafv
// int t;
// cin >> t;
// while(t--){
solve();
// }
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |