Submission #138774

#	Time	Username	Problem	Language	Result	Execution time	Memory
138774		Minnakhmetov	Virus Experiment (JOI19_virus)	C++14	0 / 100	2035 ms	262148 KiB

virus

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()


struct Node {
    int left, right, inner, len;
};

const int N = 2e5 + 5, Z = 51, INF = 2e9;

string s;
char dir[5] = "WESN";
int m, r, c;
int a[N], resistance[Z][Z], mask[Z][Z], last_ch[Z][Z], 
        dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
Node tail[Z][Z];
bool infected[Z][Z];


Node operator + (Node a, Node b) {
    Node c;
    c.len = a.len + b.len;
    c.inner = max(a.inner, b.inner);
    c.inner = max(c.inner, a.right + b.left);
    c.left = a.left + (a.inner == a.len ? b.left : 0);
    c.right = b.right + (b.inner == b.len ? a.right : 0);
    return c;
}

struct SegTree {
    Node t[N * 4];
    void build(int v, int L, int R) {
        if (L == R) {
            t[v] = {a[L], a[L], a[L], 1};
        }
        else {
            int m = (L + R) >> 1;
            build(v * 2, L, m);
            build(v * 2 + 1, m + 1, R);
            t[v] = t[v * 2] + t[v * 2 + 1];
        }
    }
    Node getFirstGreaterOrEqual(int x, int y, int v = 1, int L = 0, int R = m + m - 1) {
        if (R < x)
            return { 0, 0, 0, 0 };

        if (L == R)
            return t[v].inner >= y ? Node{ L, -1 } : t[v];

        if (L >= x && t[v].inner < y)
            return t[v];

        int m = (L + R) >> 1;

        if (x > m)
            return getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);        

        Node ln = getFirstGreaterOrEqual(x, y, v * 2, L, m);

        if (ln.right == -1)
            return ln;

        if (ln.right + t[v * 2 + 1].left >= y)
            return { m + y - ln.right, -1 };

        if (t[v * 2 + 1].inner >= y)
            return getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);

        return ln + t[v * 2 + 1];
    }

    Node getSum(int l, int r, int v = 1, int L = 0, int R = m + m - 1) {
        if (l > r)
            return { 0, 0, 0, 0 };
        if (l == L && r == R)
            return t[v];
        int m = (L + R) >> 1;
        return getSum(l, min(m, r), v * 2, L, m) +
            getSum(max(m + 1, l), r, v * 2 + 1, m + 1, R);
    }

    Node que(int l, int r) {
        int cur_len = r - l + 1;

        if (t[1].inner == t[1].len)
            return { cur_len, cur_len, cur_len, cur_len };

        if (cur_len >= m)
            l = r - m + 2;

        if (l > r)
            return { 0, 0, 0, 0 };

        r %= m;
        l %= m;
        if (l > r)
            r += m;

        return getSum(l, r);
    }
    // void print(int v, int L, int R) {
    //     cout << L << " " << R << "\n" << t[v].left << " " << t[v].inner << " " << t[v].right << " " << t[v].len << "\n\n";
    //     if (L != R) {
    //         int m = (L + R) >> 1;
    //         print(v * 2, L, m);
    //         print(v * 2 + 1, m + 1, R);
    //     }
    // }
} t[1 << 4];

struct Event {
    int t, x, y;
    bool operator < (const Event &oth) const {
        return t > oth.t;
    }
};

priority_queue<Event> pq;

int infected_count = 0;

void eventHappens(Event e) {
    if (infected[e.x][e.y])
        return;

    infected[e.x][e.y] = 1;

    infected_count++;

    for (int i = 0; i < 4; i++) {
        int p = e.x + dx[i],
            q = e.y + dy[i];

        if (p >= 0 && p < r && q >= 0 && q < c &&
            !infected[p][q] && resistance[p][q] != 0) {

//            cout << e.x << " " << e.y << " " << p << " " << q << " " << e.t << "\n";

            mask[p][q] |= 1 << i;

            tail[p][q] = tail[p][q] + t[mask[p][q]].que(last_ch[p][q] + 1, e.t);

            last_ch[p][q] = e.t;

            int new_expected_time = INF, rest = resistance[p][q] - tail[p][q].right;

            if (t[mask[p][q]].t[1].inner == m + m) {
                new_expected_time = e.t + rest;
            }
            else {
                Node node = t[mask[p][q]].getSum((e.t + 1) % m, m + m - 1);
                if (node.left >= rest) {
                    new_expected_time = e.t + rest;
                }
                else {
                    node = t[mask[p][q]].getFirstGreaterOrEqual((e.t + 1) % m, resistance[p][q]);
                    if (node.right == -1)
                        new_expected_time = node.left - (e.t + 1) % m + 1 + e.t;
                }
            }

            if (new_expected_time != INF)
                pq.push({ new_expected_time, p, q });

          //  cout << "......\n\n";
        }
    }
}

void handle(int i, int j) {
    for (int x = 0; x < r; x++) {
        for (int y = 0; y < c; y++) {
            mask[x][y] = 0;
            last_ch[x][y] = -1;
            tail[x][y] = { 0, 0, 0, 0 };
            infected[x][y] = 0;
        }
    }

    infected_count = 0;

    pq.push({ -1, i, j });

    while (!pq.empty()) {
        Event e = pq.top();
        pq.pop();
        eventHappens(e);

        // cout << e.t << "\n";

        // for (int x = 0; x < r; x++) {
        //     for (int y = 0; y < c; y++) {
        //         cout << infected[x][y];
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
    }
}


signed main() { 
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // int n;
    // cin >> n;

    // for (int i = 0; i < n; i++)
    //     cin >> a[i];
    // t[0].build(1, 0, n - 1);

    // // t[0].print(1, 0, n - 1);

    // int q;
    // cin >> q;

    // while (q--) {
    //     int x, y;
    //     cin >> x >> y;
    //     x--;
    //     Node ans = t[0].que(x, y, 1, 0, n - 1);
    //     if (ans.right == -1)
    //         cout << ans.left + 1 << "\n";
    //     else
    //         cout << -1 << "\n";
    // }

    // return 0;

    cin >> m >> r >> c >> s;


    for (char &c : s) {
        c = find(dir, dir + 4, c) - dir;
    }

    s += s;

    for (int i = 0; i < (1 << 4); i++) {
        for (int j = 0; j < m + m; j++) {
            a[j] = (i >> s[j]) & 1;
        }
        t[i].build(1, 0, m + m - 1);
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> resistance[i][j];
        }
    }

    // handle(0, 0);

    // return 0;

    int mn = INF, ct = 0;


    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (resistance[i][j] != 0) {
                handle(i, j);

                if (infected_count < mn) {
                    mn = infected_count;
                    ct = 0;
                }
                if (infected_count == mn)
                    ct++;

                //cout << i + 1 << " " << j + 1 << " : " << infected_count << "\n";
            }
        }
    }

    cout << mn << "\n" << ct;



    return 0;
}

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