Unfortunately we were unable to fully decode your file, as it is not encoded in UTF-8.
You can try to decode it yourself by downloading it here.
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int M = 1048576; const int DM = 2097152; int n, N, a, b, poprzednik, g; int C[2100000]; int D[2100000]; int W[2100000]; int liczba[1000005]; int sposoby[1000005]; int nieujemne[1000005]; int wynik[1000005]; int s; const int INF = 1000000001; // MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka void Set(int p,int v) { for(p+=s, W[p]=v, p>>=1; p>0; p>>=1) W[p] = max(W[p<<1], W[(p<<1)+1]); } int Find1(int p, int k) { int m = -INF; p+=s; k+=s; while(p<k) { if((p&1)==1) m=max(m,C[p++]); if((k&1)==0) m=max(m,C[k--]); p>>=1; k>>=1; } if(p==k) m=max(m,C[p]); return m; } int Find2(int p, int k) { int m = INF; p+=s; k+=s; while(p<k) { if((p&1)==1) m=min(m,D[p++]); if((k&1)==0) m=min(m,D[k--]); p>>=1; k>>=1; } if(p==k) m=min(m,D[p]); return m; } // MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka int main () { s = M; scanf("%d",&n); N = n + M; for (int i = M; i < N; ++i) scanf("%d%d",&C[i],&D[i]); for (int i = M - 1; i > 0; --i) C[i] = max(C[i << 1], C[(i << 1) | 1]); for (int i = N; i < DM; ++i) D[i] = INF; for (int i = M - 1; i > 0; --i) D[i] = min(D[i << 1], D[(i << 1) | 1]); for (int i = 1; i < DM; ++i) W[i] = -1; sposoby[n] = 1; nieujemne[n] = n; Set(n, 0); for (int i = 0; i < n; ++i) liczba[i] = -1; for (int i = n - 1; i >= 0; --i) { a = 0; b = n; poprzednik = i; for (int j = i + 1; j <= n; ) { j = nieujemne[j]; if (liczba[i] > wynik[j] + 1) break; int g = j + s; while (W[g] < liczba[i] - 1) { if (g & 1) g++; else (g >>= 1); } while (g < s) { g <<= 1; if (W[g] < liczba[i] - 1) g |= 1; } j = g - s; a = max(a, Find1(poprzednik, j - 1)); b = min(b, Find2(poprzednik, j - 1)); poprzednik = j; if (a > b) break; if (b < j - i) break; if (j - i < a) { j = a + i; continue; } if (liczba[j] >= liczba[i]) { liczba[i] = liczba[j] + 1; sposoby[i] = sposoby[j]; } else { sposoby[i] += sposoby[j]; if (sposoby[i] >= 1000000007) sposoby[i] -= 1000000007; } j++; } if (liczba[i] == -1) nieujemne[i] = nieujemne[i + 1]; else nieujemne[i] = i; if (liczba[i] > wynik[i + 1]) wynik[i] = liczba[i]; else wynik[i] = wynik[i + 1]; if (liczba[i] != -1) Set(i, liczba[i]); } if (liczba[0] == -1) printf("NIE\n"); else printf("%d %d\n", liczba[0], sposoby[0]); 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 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 | #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int M = 1048576; const int DM = 2097152; int n, N, a, b, poprzednik, g; int C[2100000]; int D[2100000]; int W[2100000]; int liczba[1000005]; int sposoby[1000005]; int nieujemne[1000005]; int wynik[1000005]; int s; const int INF = 1000000001; // MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka void Set(int p,int v) { for(p+=s, W[p]=v, p>>=1; p>0; p>>=1) W[p] = max(W[p<<1], W[(p<<1)+1]); } int Find1(int p, int k) { int m = -INF; p+=s; k+=s; while(p<k) { if((p&1)==1) m=max(m,C[p++]); if((k&1)==0) m=max(m,C[k--]); p>>=1; k>>=1; } if(p==k) m=max(m,C[p]); return m; } int Find2(int p, int k) { int m = INF; p+=s; k+=s; while(p<k) { if((p&1)==1) m=min(m,D[p++]); if((k&1)==0) m=min(m,D[k--]); p>>=1; k>>=1; } if(p==k) m=min(m,D[p]); return m; } // MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka int main () { s = M; scanf("%d",&n); N = n + M; for (int i = M; i < N; ++i) scanf("%d%d",&C[i],&D[i]); for (int i = M - 1; i > 0; --i) C[i] = max(C[i << 1], C[(i << 1) | 1]); for (int i = N; i < DM; ++i) D[i] = INF; for (int i = M - 1; i > 0; --i) D[i] = min(D[i << 1], D[(i << 1) | 1]); for (int i = 1; i < DM; ++i) W[i] = -1; sposoby[n] = 1; nieujemne[n] = n; Set(n, 0); for (int i = 0; i < n; ++i) liczba[i] = -1; for (int i = n - 1; i >= 0; --i) { a = 0; b = n; poprzednik = i; for (int j = i + 1; j <= n; ) { j = nieujemne[j]; if (liczba[i] > wynik[j] + 1) break; int g = j + s; while (W[g] < liczba[i] - 1) { if (g & 1) g++; else (g >>= 1); } while (g < s) { g <<= 1; if (W[g] < liczba[i] - 1) g |= 1; } j = g - s; a = max(a, Find1(poprzednik, j - 1)); b = min(b, Find2(poprzednik, j - 1)); poprzednik = j; if (a > b) break; if (b < j - i) break; if (j - i < a) { j = a + i; continue; } if (liczba[j] >= liczba[i]) { liczba[i] = liczba[j] + 1; sposoby[i] = sposoby[j]; } else { sposoby[i] += sposoby[j]; if (sposoby[i] >= 1000000007) sposoby[i] -= 1000000007; } j++; } if (liczba[i] == -1) nieujemne[i] = nieujemne[i + 1]; else nieujemne[i] = i; if (liczba[i] > wynik[i + 1]) wynik[i] = liczba[i]; else wynik[i] = wynik[i + 1]; if (liczba[i] != -1) Set(i, liczba[i]); } if (liczba[0] == -1) printf("NIE\n"); else printf("%d %d\n", liczba[0], sposoby[0]); return 0; } |