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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 #include using namespace std; int main(){ int n; cin >> n; vector V(n+1); vector pom(n+1); V[0] = 0; for(int i = 1; i<=n; ++i) cin >> V[i]; long double maks = 2*n + 1; long double pomn = 1; long double med = n; long long ans = 0; vector > p1(n+1); vector > p2(n+1); while(med >= (long double)(n+1)/2 && pomn <= n){ //cout << "pomn: " << pomn << ", med: " << med << " -> "; if(((long long)pomn)%2 == 1){ for(int i = 1; i<=n; ++i){ if(V[i]>=med) pom[i] = pom[i-1]+1; else pom[i] = pom[i-1]-1; //cout << pom[i] << " "; } //cout << "\n"; for(int i = 1; i+pomn<=n+1; ++i){ if(pom[i+pomn-1]-pom[i-1] >= 0){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } } }else if(((long long)pomn)%2 == 0){ for(int i = (pomn/2); i+(pomn/2)<=n; ++i){ //cout << "i w forze dla parzystych to: " << i << "\n"; if(pomn == 2){ if(V[i+1-(pomn/2)] > V[i+(pomn/2)]){ p2[i].insert(V[i+1-(pomn/2)]); p1[i].insert(V[i+(pomn/2)]); }else{ p1[i].insert(V[i+1-(pomn/2)]); p2[i].insert(V[i+(pomn/2)]); } if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else{ long double pmed = *(--p1[i].end()); pmed += *(p2[i].begin()); pmed /= 2; if(V[i+1-(pomn/2)] < pmed && V[i+(pomn/2)] < pmed){ // oba do lewej czesci p2[i].insert(*p1[i].rbegin()); set::iterator it = p1[i].end(); --it; p1[i].erase(it); // TUTAJ END! p1[i].insert(V[i+1-(pomn/2)]); p1[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] > pmed && V[i+(pomn/2)] > pmed){ p1[i].insert(*p2[i].begin()); p2[i].erase(p2[i].begin()); p2[i].insert(V[i+1-(pomn/2)]); p2[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] > pmed && V[i+(pomn/2)] < pmed){ p2[i].insert(V[i+1-(pomn/2)]); p1[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] < pmed && V[i+(pomn/2)] > pmed){ p1[i].insert(V[i+1-(pomn/2)]); p2[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] > pmed && V[i+(pomn/2)] == pmed){ p2[i].insert(V[i+1-(pomn/2)]); p1[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] < pmed && V[i+(pomn/2)] == pmed){ p1[i].insert(V[i+1-(pomn/2)]); p2[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] == pmed && V[i+(pomn/2)] < pmed){ p2[i].insert(V[i+1-(pomn/2)]); p1[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else if(V[i+1-(pomn/2)] == pmed && V[i+(pomn/2)] > pmed){ p1[i].insert(V[i+1-(pomn/2)]); p2[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } }else{ p1[i].insert(V[i+1-(pomn/2)]); p2[i].insert(V[i+(pomn/2)]); if(((*p1[i].rbegin())+(*p2[i].begin()))/2 == med){ ans++; //cout << "l: " << i << ", p: " << i+pomn-1 << "\n"; } } } //cout << "\n"; } } pomn++; med -= 0.5; } cout << maks << " " << ans << "\n"; }