Submission #434048

#	Time	Username	Problem	Language	Result	Execution time	Memory
434048		dxz05	Virus Experiment (JOI19_virus)	C++14	14 / 100	151 ms	6980 KiB

virus

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 888;

#define MP make_pair
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int n, m;
int a[N][N];

int t[N][12], Log[N];
void build(int m, int row){
    for (int i = 2; i <= m; i++){
        Log[i] = Log[i / 2] + 1;
    }

    for (int i = 0; i < 12; i++){
        for (int j = 1; j <= m; j++){
            if (i == 0){
                t[j][i] = (a[row][j] > 0 ? a[row][j] : 2e9);
            } else {
                int x = 1 << i;
                t[j][i] = max(t[j][i - 1], t[j + x - 1][i - 1]);
            }
        }
    }
}

int get(int l, int r){
    if (l == r) return t[l][0];
    int x = Log[r - l + 1];
    return max(t[l][x], t[r - (1 << x) + 1][x]);
}

void solve(){
    int len; string s;
    cin >> len >> n >> m >> s;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    s += s;
    len <<= 1;

    int EE = 0, WW = 0;
    for (int i = 0; i < len; i++){
        if (s[i] != 'E') continue;
        int j = i;
        while (j < len && s[j] == 'E') j++;
        j--;
        EE = max(EE, j - i + 1);
        i = j;
    }

    for (int i = 0; i < len; i++){
        if (s[i] != 'W') continue;
        int j = i;
        while (j < len && s[j] == 'W') j++;
        j--;
        WW = max(WW, j - i + 1);
        i = j;
    }

    if (EE == len) EE = 1e9;
    if (WW == len) WW = 1e9;

    build(m, 4);

    int ans = 1e9, cnt = 0;
    for (int i = 1; i <= n; i++){
        build(m, i);
        for (int j = 1; j <= m; j++){
            if (a[i][j] == 0) continue;

            int lf = j, rg = j;

            int l = 1, r = j - 1;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (get(mid, j - 1) != 0 && get(mid, j - 1) <= EE){
                    lf = mid;
                    r = mid - 1;
                } else l = mid + 1;
            }

            l = j + 1, r = m;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (get(j + 1, mid) != 0 && get(j + 1, mid) <= WW){
                    rg = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }

            if (rg - lf + 1 < ans){
                ans = rg - lf + 1;
                cnt = 1;
            } else if (rg - lf + 1 == ans) cnt++;

            //cout << lf << ',' << rg << ' ';

        }
        //cout << endl;
    }

    cout << ans << endl << cnt << endl;

}

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("output.txt", "w", stdout);
    int tests = 1;
   // cin >> tests;

    while (tests--){
        solve();
    }

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80