8042 | 2024. 01. 12 11:22:23 | Ablablabla | Rendező robot (80 pont) | cpp17 | Hibás válasz 5/80 | 275ms | 28508 KiB |
#include <bits/stdc++.h>
using namespace std;
struct segTree{
int meret = 1;
vector<int> fa;
void letrehoz(int n){
while(meret < n){
meret *= 2;
}
fa.assign(2 * meret - 1, 0);
}
void tisztit(){
fa.assign(2 * meret - 1, 0);
}
int valtoztat(int a, int b, int ind, int cel){
if(cel < a || b < cel){
return fa[ind];
} else if(a == b){
return fa[ind] = 1;
}
int k = (a + b) / 2;
return fa[ind] = valtoztat(a, k, 2 * ind + 1, cel) + valtoztat(k + 1, b, 2 * ind + 2, cel);
}
int keres(int a, int b, int ind, int kezd, int veg){
if(veg < a || b < kezd){
return 0;
} else if(kezd <= a && b <= veg){
return fa[ind];
}
int k = (a + b) / 2;
return keres(a, k, 2 * ind + 1, kezd, veg) + keres(k + 1, b, 2 * ind + 2, kezd, veg);
}
};
int main()
{
int n;
cin >> n;
vector<int> ind(n + 1, 0);
for(int i = 1; i <= n; i++){
int a;
cin >> a;
ind[a] = i;
}
segTree fa;
fa.letrehoz(n);
vector<int> elol(n + 2, 0);
vector<int> hatul(n + 2, 0);
int streak = 0;
for(int i = 1; i <= n; i++){
int ujInd = ind[i] + fa.keres(0, fa.meret - 1, 0, ind[i], n - 1);
elol[i] = elol[i - 1];
if(i != ujInd){
fa.valtoztat(0, fa.meret - 1, 0, ind[i] - 1);
elol[i] += streak + 1;
streak = 0;
} else{
streak++;
}
}
fa.tisztit();
streak = 0;
for(int i = n; i >= 1; i--){
int ujInd = ind[i] - fa.keres(0, fa.meret - 1, 0, 0, max(ind[i] - 2, 0));
hatul[i] = hatul[i + 1];
if(i != ujInd){
fa.valtoztat(0, fa.meret - 1, 0, ind[i] - 1);
hatul[i] += streak + 1;
streak = 0;
} else{
streak++;
}
}
int mini = 2e9 + 7;
for(int i = 0; i <= n; i++){
int felul = (elol[i] == 0 ? 0 : 2 * elol[i] - 1);
int alul = (hatul[i + 1] == 0 ? 0 : 2 * hatul[i + 1]);
mini = min(mini, max(felul, alul));
}
cout << mini << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 5/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1852 KiB | |||
2 | Hibás válasz | 0/0 | 3ms | 2108 KiB | |||
3 | Hibás válasz | 0/2 | 3ms | 2344 KiB | |||
4 | Hibás válasz | 0/3 | 3ms | 2428 KiB | |||
5 | Elfogadva | 3/3 | 3ms | 2636 KiB | |||
6 | Hibás válasz | 0/2 | 4ms | 2928 KiB | |||
7 | Hibás válasz | 0/2 | 4ms | 3148 KiB | |||
8 | Hibás válasz | 0/2 | 4ms | 3384 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3464 KiB | |||
10 | Hibás válasz | 0/2 | 4ms | 3424 KiB | |||
11 | Hibás válasz | 0/2 | 4ms | 3632 KiB | |||
12 | Hibás válasz | 0/2 | 4ms | 4008 KiB | |||
13 | Hibás válasz | 0/2 | 4ms | 3976 KiB | |||
14 | Hibás válasz | 0/2 | 4ms | 3844 KiB | |||
15 | Hibás válasz | 0/2 | 4ms | 3852 KiB | |||
16 | Hibás válasz | 0/2 | 4ms | 3832 KiB | |||
17 | Hibás válasz | 0/2 | 4ms | 4312 KiB | |||
18 | Hibás válasz | 0/4 | 263ms | 14216 KiB | |||
19 | Hibás válasz | 0/4 | 275ms | 15300 KiB | |||
20 | Hibás válasz | 0/4 | 226ms | 16560 KiB | |||
21 | Hibás válasz | 0/4 | 189ms | 17820 KiB | |||
22 | Hibás válasz | 0/4 | 194ms | 19360 KiB | |||
23 | Hibás válasz | 0/4 | 207ms | 20656 KiB | |||
24 | Hibás válasz | 0/4 | 230ms | 21808 KiB | |||
25 | Hibás válasz | 0/4 | 266ms | 23128 KiB | |||
26 | Hibás válasz | 0/4 | 209ms | 24532 KiB | |||
27 | Hibás válasz | 0/4 | 246ms | 25812 KiB | |||
28 | Hibás válasz | 0/4 | 209ms | 27192 KiB | |||
29 | Hibás válasz | 0/4 | 210ms | 28508 KiB |