Submission #138818

#	Time	Username	Problem	Language	Result	Execution time	Memory
138818		Minnakhmetov	Virus Experiment (JOI19_virus)	C++14	0 / 100	2065 ms	51576 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], rip[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 {
    int t[N * 4], lens[N];
    int size = 0;

    pair<int, int> segs[N];

    bool full = false;

    void build(int v, int L, int R) {
        if (L == R) {
            t[v] = lens[L];
        }
        else {
            int m = (L + R) >> 1;
            build(v * 2, L, m);
            build(v * 2 + 1, m + 1, R);
            t[v] = max(t[v * 2], t[v * 2 + 1]);
        }
    }

    void init(int n) {
        for (int i = 0, j = -1; i < n; i++) {
            if (a[i]) {
                if (i == n - 1 || a[i + 1] == 0) {
                    segs[size] = {j + 1, i};
                    lens[size] = i - j;
                    size++;
                }
            }
            else {
                j = i;
            }

        }

        // for (int i = 0; i < size; i++) {
        //     cout << lens[i] << " ";
        // }
        // cout << "\n";

        if (size > 0)
            build(1, 0, size - 1);

        full = (size == 1 && lens[0] == m + m);
    }

    int getFirstGreaterOrEqual(int x, int y, int v, int L, int R) {
        if (R < x)
            return -1;
        if (t[v] < y)
            return -1;
        if (L == R)
            return L;
        int m = (L + R) >> 1,
            ans = getFirstGreaterOrEqual(x, y, v * 2, L, m);
        if (ans == -1)
            ans = getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);
        return ans;
    }

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

    int getFirstAppropriate(int x, int y) {
        int j = upper_bound(segs, segs + size, make_pair(x + 1, -1)) - segs;
        if (j > 0 && segs[j - 1].second - x + 1 >= y)
             return x + y - 1;
        int k = getFirstGreaterOrEqual(j, y, 1, 0, size - 1);
        if (k == -1)
            return -1;
        return segs[k].first + y - 1;
    }

    Node getSum(int l, int r) {
        Node res = { 0, 0, 0, r - l + 1 };

        int j = upper_bound(segs, segs + size, make_pair(l + 1, -1)) - segs,
            k = upper_bound(segs, segs + size, make_pair(r + 1, -1)) - segs;

        if (j > 0)
            res.left = max(0, segs[j - 1].second - l + 1);
        if (k > 0 && segs[k - 1].second >= r) {
            res.right = segs[k - 1].second - r + 1;
            k -= 2;
        }
        else {
            k--;
        }
        res.inner = getMax(j, k, 1, 0, size - 1);
        return res;
    }

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

        if (full)
            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);
    }
} 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 && !rip[p][q]) {

           // cout << e.x << " " << e.y << " " << p << " " << q << "\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]].full) {
                new_expected_time = e.t + rest;
                rip[p][q] = 1;
            }
            else {
                Node node = t[mask[p][q]].getSum((e.t + 1) % m, m + m - 1);
                // cout << (e.t + 1) % m << " " << m + m - 1 << " " << node.left << " " << node.inner << " " << node.right << "\n";
                if (node.left >= rest) {
                    new_expected_time = e.t + rest;
                    rip[p][q] = 1;
                }
                else {
                    int k = t[mask[p][q]].getFirstAppropriate((e.t + 1) % m, resistance[p][q]);
                    if (k != -1)
                        new_expected_time = k - (e.t + 1) % m + 1 + e.t;
                }
            }

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


int mn = INF, ct = 0;

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;
            rip[x][y] = 0;
        }
    }

    infected_count = 0;

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

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

        if (infected_count > mn)
            break;
    }

    pq = priority_queue<Event>();
}


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].init(n);

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

    // while (q--) {
    //     int x, y;
    //     cin >> x >> y;
    //     cout << t[0].getFirstAppropriate(x - 1, y) + 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].init(m + m);
    }

    pair<int, int> order[Z * Z];

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

    // handle(0, 0);

    // cout << infected_count << "\n";

    // return 0;

    mt19937 rnd(time(0));   
    shuffle(order, order + r * c, rnd);

    for (int x = 0; x < r * c; x++) {
        int i = order[x].first,
            j = order[x].second;

        if (resistance[i][j] != 0) {
            handle(i, j);

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

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

    return 0;
}

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