#include <iostream> #include <vector> #include <stdint.h> #include <array> using namespace std; int main() { int32_t n; cin>>n; vector<int32_t> oceny(n), pozycje(n+1); for (int32_t ii=0; ii<n; ii++) { cin>>oceny[ii]; pozycje[oceny[ii]]=ii; // ii-ty element zawiera pozycje oceny = ii } int32_t l=pozycje[n], r=pozycje[n], p; uint64_t licznik=1; // przedzial zawierajacy tylko najwyzsza ocene jest dobrym rozwiazaniem for (int32_t ocena=n-1; ocena>0; ocena--) { p=pozycje[ocena]; l = min(l, p); r = max(r, p); int32_t odleglosc = r-l+1; for (uint8_t jj=2; jj>=1; jj--) { //mozliwe dlugosci przedzialu zawierajacego k=n-ii+1 najwyzszych ocen to (2*k-1) i (2*k-2) int32_t dlPrzedzialu = 2*(n-ocena+1)-jj; if (dlPrzedzialu>n) { ocena=0; // break outer loop break; } if (odleglosc <=dlPrzedzialu) { int32_t liczbaPozycji = dlPrzedzialu - odleglosc + 1; if (r+1 - dlPrzedzialu <0) liczbaPozycji += r+1-dlPrzedzialu; if (l-1 + dlPrzedzialu > n-1) liczbaPozycji += n-l-dlPrzedzialu; licznik += liczbaPozycji; } } } //punkty = n + 2*median(1,2,...,n) = 2*n+1 cout<< 2*n+1<<' '<<licznik <<endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> #include <vector> #include <stdint.h> #include <array> using namespace std; int main() { int32_t n; cin>>n; vector<int32_t> oceny(n), pozycje(n+1); for (int32_t ii=0; ii<n; ii++) { cin>>oceny[ii]; pozycje[oceny[ii]]=ii; // ii-ty element zawiera pozycje oceny = ii } int32_t l=pozycje[n], r=pozycje[n], p; uint64_t licznik=1; // przedzial zawierajacy tylko najwyzsza ocene jest dobrym rozwiazaniem for (int32_t ocena=n-1; ocena>0; ocena--) { p=pozycje[ocena]; l = min(l, p); r = max(r, p); int32_t odleglosc = r-l+1; for (uint8_t jj=2; jj>=1; jj--) { //mozliwe dlugosci przedzialu zawierajacego k=n-ii+1 najwyzszych ocen to (2*k-1) i (2*k-2) int32_t dlPrzedzialu = 2*(n-ocena+1)-jj; if (dlPrzedzialu>n) { ocena=0; // break outer loop break; } if (odleglosc <=dlPrzedzialu) { int32_t liczbaPozycji = dlPrzedzialu - odleglosc + 1; if (r+1 - dlPrzedzialu <0) liczbaPozycji += r+1-dlPrzedzialu; if (l-1 + dlPrzedzialu > n-1) liczbaPozycji += n-l-dlPrzedzialu; licznik += liczbaPozycji; } } } //punkty = n + 2*median(1,2,...,n) = 2*n+1 cout<< 2*n+1<<' '<<licznik <<endl; return 0; } |