//Pawel Kura #include <cstdio> #include <vector> #include <algorithm> //#define int long long using namespace std; typedef long long LL; struct sciezka { vector<int> a; vector<vector<int>> kto; }; int n; const int MAXN = 1000000; int m; char s[MAXN + 10]; int h[MAXN + 10]; vector<sciezka> sciezki; int reszta[MAXN]; LL kiedy[MAXN]; int mem[4*MAXN]; void rozwal(const sciezka &sci) { const auto &a = sci.a; int s = a.size(); vector<int> sumy; int prev = 0; for (int i = 0; i < 2 * s - 1; i++) { prev += a[i % s]; sumy.push_back(prev); } static vector<pair<int,int>> deq(2 * MAXN - 1); int p, q; p = q = deq.size(); for (int i = 2 * s - 2; i >= s; i--) { while (p < q && deq[p].first >= sumy[i]) p++; deq[--p] = {sumy[i], i}; mem[-sumy[i]+2*MAXN] = p; } for (int i = s - 1; i >= 0; i--) { while (p < q && deq[q-1].second >= i + s) q--; while (p < q && deq[p].first >= sumy[i]) p++; deq[--p] = {sumy[i], i}; mem[-sumy[i]+2*MAXN] = p; int fix = (i == 0 ? 0 : sumy[i-1]); int mi = deq[q-1].first - fix; int su = sumy[i + s - 1] - fix; for (auto k: sci.kto[i]) { int v = h[k]; if (su >= 0) { if (v + mi > 0) { kiedy[k] = -1; } else { int z = mem[v-fix+2*MAXN]; auto pos = deq[z].second - i; kiedy[k] = k + 1 + (LL)pos * n; } } else { int licz = max(0, v + mi); int mian = -su; int obroty = (licz + mian - 1)/mian; LL r = v + (LL)obroty * su; int z = mem[r-fix+2*MAXN]; int pos = deq[z].second - i; kiedy[k] = k + 1 + 1LL * (pos + 1LL * obroty * s) * n; } } } } int gcd(int a, int b) { if (a == 0) return b; return gcd(b%a, a); } signed main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &h[i]); scanf("%d", &m); scanf(" %s", s); sciezki.resize(gcd(n, m)); for (int i = 0; i < sciezki.size(); i++) { int k = i; int z = 0; sciezki[i].a.resize(m / sciezki.size()); do { sciezki[i].a[z] = s[k] == 'W' ? 1 : -1; reszta[k] = z++; k = (k + n) % m; } while (k != i); sciezki[i].kto.resize(sciezki[i].a.size()); } for (int i = 0; i < n; i++) { sciezki[i % sciezki.size()].kto[reszta[i%m]].push_back(i); } for (int i = 0; i < sciezki.size(); i++) { rozwal(sciezki[i]); } LL res = -1; for (int i = 0; i < n; i++) { if (kiedy[i] != -1 && (kiedy[i] < res || res == -1)) res = kiedy[i]; } printf("%lld\n", res); 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 | //Pawel Kura #include <cstdio> #include <vector> #include <algorithm> //#define int long long using namespace std; typedef long long LL; struct sciezka { vector<int> a; vector<vector<int>> kto; }; int n; const int MAXN = 1000000; int m; char s[MAXN + 10]; int h[MAXN + 10]; vector<sciezka> sciezki; int reszta[MAXN]; LL kiedy[MAXN]; int mem[4*MAXN]; void rozwal(const sciezka &sci) { const auto &a = sci.a; int s = a.size(); vector<int> sumy; int prev = 0; for (int i = 0; i < 2 * s - 1; i++) { prev += a[i % s]; sumy.push_back(prev); } static vector<pair<int,int>> deq(2 * MAXN - 1); int p, q; p = q = deq.size(); for (int i = 2 * s - 2; i >= s; i--) { while (p < q && deq[p].first >= sumy[i]) p++; deq[--p] = {sumy[i], i}; mem[-sumy[i]+2*MAXN] = p; } for (int i = s - 1; i >= 0; i--) { while (p < q && deq[q-1].second >= i + s) q--; while (p < q && deq[p].first >= sumy[i]) p++; deq[--p] = {sumy[i], i}; mem[-sumy[i]+2*MAXN] = p; int fix = (i == 0 ? 0 : sumy[i-1]); int mi = deq[q-1].first - fix; int su = sumy[i + s - 1] - fix; for (auto k: sci.kto[i]) { int v = h[k]; if (su >= 0) { if (v + mi > 0) { kiedy[k] = -1; } else { int z = mem[v-fix+2*MAXN]; auto pos = deq[z].second - i; kiedy[k] = k + 1 + (LL)pos * n; } } else { int licz = max(0, v + mi); int mian = -su; int obroty = (licz + mian - 1)/mian; LL r = v + (LL)obroty * su; int z = mem[r-fix+2*MAXN]; int pos = deq[z].second - i; kiedy[k] = k + 1 + 1LL * (pos + 1LL * obroty * s) * n; } } } } int gcd(int a, int b) { if (a == 0) return b; return gcd(b%a, a); } signed main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &h[i]); scanf("%d", &m); scanf(" %s", s); sciezki.resize(gcd(n, m)); for (int i = 0; i < sciezki.size(); i++) { int k = i; int z = 0; sciezki[i].a.resize(m / sciezki.size()); do { sciezki[i].a[z] = s[k] == 'W' ? 1 : -1; reszta[k] = z++; k = (k + n) % m; } while (k != i); sciezki[i].kto.resize(sciezki[i].a.size()); } for (int i = 0; i < n; i++) { sciezki[i % sciezki.size()].kto[reszta[i%m]].push_back(i); } for (int i = 0; i < sciezki.size(); i++) { rozwal(sciezki[i]); } LL res = -1; for (int i = 0; i < n; i++) { if (kiedy[i] != -1 && (kiedy[i] < res || res == -1)) res = kiedy[i]; } printf("%lld\n", res); return 0; } |