oj.uz

Submission #907490

# Submission time Handle Problem Language Result Execution time Memory
907490 2024-01-15T17:42:47 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++17
27 / 100
 5000 ms 57620 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 = 2000;
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 54 ms 23552 KB Output is correct
2 Correct 66 ms 24836 KB Output is correct
3 Correct 61 ms 24300 KB Output is correct
4 Correct 74 ms 24068 KB Output is correct
5 Correct 67 ms 24580 KB Output is correct
6 Correct 54 ms 23868 KB Output is correct
7 Correct 67 ms 24632 KB Output is correct
8 Correct 67 ms 24576 KB Output is correct
9 Correct 73 ms 24576 KB Output is correct
10 Correct 71 ms 25176 KB Output is correct
11 Correct 68 ms 24580 KB Output is correct
12 Correct 73 ms 25484 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 22788 KB Output is correct
2 Correct 58 ms 22788 KB Output is correct
3 Correct 63 ms 22912 KB Output is correct
4 Correct 61 ms 24320 KB Output is correct
5 Correct 65 ms 24828 KB Output is correct
6 Correct 67 ms 24056 KB Output is correct
7 Correct 92 ms 25280 KB Output is correct
8 Correct 102 ms 26304 KB Output is correct
9 Correct 92 ms 25544 KB Output is correct
10 Correct 115 ms 28156 KB Output is correct
11 Correct 99 ms 26972 KB Output is correct
12 Correct 119 ms 29220 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 27316 KB Output is correct
2 Correct 4019 ms 52224 KB Output is correct
3 Correct 2825 ms 55384 KB Output is correct
4 Correct 2783 ms 57620 KB Output is correct
5 Correct 4006 ms 52664 KB Output is correct
6 Correct 1253 ms 28912 KB Output is correct
7 Execution timed out 5046 ms 55180 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 23552 KB Output is correct
2 Correct 66 ms 24836 KB Output is correct
3 Correct 61 ms 24300 KB Output is correct
4 Correct 74 ms 24068 KB Output is correct
5 Correct 67 ms 24580 KB Output is correct
6 Correct 54 ms 23868 KB Output is correct
7 Correct 67 ms 24632 KB Output is correct
8 Correct 67 ms 24576 KB Output is correct
9 Correct 73 ms 24576 KB Output is correct
10 Correct 71 ms 25176 KB Output is correct
11 Correct 68 ms 24580 KB Output is correct
12 Correct 73 ms 25484 KB Output is correct
13 Correct 1104 ms 27232 KB Output is correct
14 Execution timed out 5012 ms 51280 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 23552 KB Output is correct
2 Correct 66 ms 24836 KB Output is correct
3 Correct 61 ms 24300 KB Output is correct
4 Correct 74 ms 24068 KB Output is correct
5 Correct 67 ms 24580 KB Output is correct
6 Correct 54 ms 23868 KB Output is correct
7 Correct 67 ms 24632 KB Output is correct
8 Correct 67 ms 24576 KB Output is correct
9 Correct 73 ms 24576 KB Output is correct
10 Correct 71 ms 25176 KB Output is correct
11 Correct 68 ms 24580 KB Output is correct
12 Correct 73 ms 25484 KB Output is correct
13 Correct 58 ms 22788 KB Output is correct
14 Correct 58 ms 22788 KB Output is correct
15 Correct 63 ms 22912 KB Output is correct
16 Correct 61 ms 24320 KB Output is correct
17 Correct 65 ms 24828 KB Output is correct
18 Correct 67 ms 24056 KB Output is correct
19 Correct 92 ms 25280 KB Output is correct
20 Correct 102 ms 26304 KB Output is correct
21 Correct 92 ms 25544 KB Output is correct
22 Correct 115 ms 28156 KB Output is correct
23 Correct 99 ms 26972 KB Output is correct
24 Correct 119 ms 29220 KB Output is correct
25 Correct 1075 ms 27316 KB Output is correct
26 Correct 4019 ms 52224 KB Output is correct
27 Correct 2825 ms 55384 KB Output is correct
28 Correct 2783 ms 57620 KB Output is correct
29 Correct 4006 ms 52664 KB Output is correct
30 Correct 1253 ms 28912 KB Output is correct
31 Execution timed out 5046 ms 55180 KB Time limit exceeded
32 Halted 0 ms 0 KB -