Submission #907489

#	Time	Username	Problem	Language	Result	Execution time	Memory
907489		LOLOLO	I want to be the very best too! (NOI17_pokemonmaster)	C++17	71 / 100	5040 ms	37292 KiB

pokemonmaster

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int M = 1e5 + 100;
const int N = M;
const int SZ = 1000;
int t[N], x[N], l[N], r[N], n, m, change[M], L[M], P[M], sz[N], y[N], p[N], C[N], ans[N];
vector <pair <int, int>> save[M];

int cov(int a, int b) {
    return (a - 1) * m + b;
}

int get(int a) {
    if (p[a] == 0)
        return a;

    return p[a] = get(p[a]);
}

int cc[N];
unordered_map <int, int> mp[N];

void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b)
        return;

    if (sz[a] < sz[b])
        swap(a, b);

    sz[a] += sz[b];
    p[b] = a;

    for (auto &x : mp[b]) {
        int &t = mp[a][x.f];
        if (t == 0 && x.s)
            cc[a]++;

        t += x.s;
    }
}

vector <vector <int>> action;

void upd(int c, int x) {
    c = get(c);

    int &t = mp[c][x];
    if (t == 0)
        cc[c]++;

    action.pb({c, x, t});
    t++;
}

void rollback() {
    while (sz(action)) {
        auto t = action.back();
        action.pop_back();
        if (t[2] == 0) {
            cc[t[0]]--;
        }

        mp[t[0]][t[1]] = t[2];
    }
}

ll solve() {
    mem(L, 0x3f);
    mem(P, 0x3f);

    int q;
    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> L[cov(i, j)];

    vector <vector <int>> edge;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i < n)
                edge.pb({max(L[cov(i + 1, j)], L[cov(i, j)]), cov(i + 1, j), cov(i, j)});

            if (j < m)
                edge.pb({max(L[cov(i, j + 1)], L[cov(i, j)]), cov(i, j + 1), cov(i, j)});
        }
    }

    sort(all(edge), [&](vector <int> a, vector <int> b) { return a[0] < b[0]; });
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> P[cov(i, j)];

    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> y[i] >> x[i] >> r[i];
    }

    for (int i = 1; i <= q; i += SZ) {
        int X = i, Y = min(q, i + SZ - 1);
        vector <int> ask, up;
        for (int j = X; j <= Y; j++) {
            if (t[j] == 2) {
                ask.pb(j);
            } else {
                up.pb(j);
                change[cov(x[j], y[j])] = 1;
            }
        }

        for (int j = X; j <= Y; j++) {
            if (t[j] == 1) {
                P[cov(x[j], y[j])] = r[j];
            } else {
                save[j - X].clear();
                for (auto t : up) {
                    save[j - X].pb({cov(x[t], y[t]), P[cov(x[t], y[t])]});
                }
            }
        }

        sort(all(ask), [&](int a, int b) { return r[a] < r[b]; });
        for (int j = 1; j <= n * m; j++) {
            mp[j].clear();
            if (change[j] == 0) {
                cc[j] = 1;
                mp[j][P[j]]++;
            } else {
                cc[j] = 0;
            }

            sz[j] = 1;
            p[j] = 0;
        }

        int j = 0;
        for (auto id : ask) {
            while (j < sz(edge) && r[id] >= edge[j][0]) {
                unite(edge[j][1], edge[j][2]);
                j++;
            }

            for (auto t : save[id - X]) {
                upd(t.f, t.s);
            }

            if (r[id] >= L[cov(x[id], y[id])])
                ans[id] = cc[get(cov(x[id], y[id]))];

            rollback();
        }

        for (auto id : up)
            change[cov(x[id], y[id])] = 0;
    }

    for (int i = 1; i <= q; i++) {
        if (t[i] == 2) {
            cout << ans[i] << "\n";
        }
    }

    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
        //cout << solve() << '\n';
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 29