oj.uz

Submission #907491

# Submission time Handle Problem Language Result Execution time Memory
907491 2024-01-15T17:43:05 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++17
27 / 100
 5000 ms 71428 KB 
#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 = 3000;
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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23868 KB Output is correct
2 Correct 65 ms 24832 KB Output is correct
3 Correct 70 ms 24368 KB Output is correct
4 Correct 58 ms 24128 KB Output is correct
5 Correct 67 ms 24640 KB Output is correct
6 Correct 66 ms 23860 KB Output is correct
7 Correct 65 ms 24584 KB Output is correct
8 Correct 73 ms 24580 KB Output is correct
9 Correct 67 ms 24580 KB Output is correct
10 Correct 82 ms 25092 KB Output is correct
11 Correct 69 ms 24640 KB Output is correct
12 Correct 79 ms 25492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 22580 KB Output is correct
2 Correct 57 ms 22788 KB Output is correct
3 Correct 61 ms 23048 KB Output is correct
4 Correct 85 ms 24572 KB Output is correct
5 Correct 72 ms 24796 KB Output is correct
6 Correct 67 ms 24044 KB Output is correct
7 Correct 97 ms 25256 KB Output is correct
8 Correct 97 ms 26880 KB Output is correct
9 Correct 105 ms 25600 KB Output is correct
10 Correct 109 ms 28368 KB Output is correct
11 Correct 100 ms 26956 KB Output is correct
12 Correct 118 ms 29368 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1473 ms 29664 KB Output is correct
2 Execution timed out 5052 ms 71428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23868 KB Output is correct
2 Correct 65 ms 24832 KB Output is correct
3 Correct 70 ms 24368 KB Output is correct
4 Correct 58 ms 24128 KB Output is correct
5 Correct 67 ms 24640 KB Output is correct
6 Correct 66 ms 23860 KB Output is correct
7 Correct 65 ms 24584 KB Output is correct
8 Correct 73 ms 24580 KB Output is correct
9 Correct 67 ms 24580 KB Output is correct
10 Correct 82 ms 25092 KB Output is correct
11 Correct 69 ms 24640 KB Output is correct
12 Correct 79 ms 25492 KB Output is correct
13 Correct 1621 ms 29276 KB Output is correct
14 Execution timed out 5027 ms 71168 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23868 KB Output is correct
2 Correct 65 ms 24832 KB Output is correct
3 Correct 70 ms 24368 KB Output is correct
4 Correct 58 ms 24128 KB Output is correct
5 Correct 67 ms 24640 KB Output is correct
6 Correct 66 ms 23860 KB Output is correct
7 Correct 65 ms 24584 KB Output is correct
8 Correct 73 ms 24580 KB Output is correct
9 Correct 67 ms 24580 KB Output is correct
10 Correct 82 ms 25092 KB Output is correct
11 Correct 69 ms 24640 KB Output is correct
12 Correct 79 ms 25492 KB Output is correct
13 Correct 56 ms 22580 KB Output is correct
14 Correct 57 ms 22788 KB Output is correct
15 Correct 61 ms 23048 KB Output is correct
16 Correct 85 ms 24572 KB Output is correct
17 Correct 72 ms 24796 KB Output is correct
18 Correct 67 ms 24044 KB Output is correct
19 Correct 97 ms 25256 KB Output is correct
20 Correct 97 ms 26880 KB Output is correct
21 Correct 105 ms 25600 KB Output is correct
22 Correct 109 ms 28368 KB Output is correct
23 Correct 100 ms 26956 KB Output is correct
24 Correct 118 ms 29368 KB Output is correct
25 Correct 1473 ms 29664 KB Output is correct
26 Execution timed out 5052 ms 71428 KB Time limit exceeded
27 Halted 0 ms 0 KB -