oj.uz

Submission #907474

# Submission time Handle Problem Language Result Execution time Memory
907474 2024-01-15T17:19:05 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++17
47 / 100
 5000 ms 29136 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 = 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) {
    return p[a] ? get(p[a]) : a;
}

int cc[N];
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]) {
        if (mp[a][x.f] == 0 && x.s)
            cc[a]++;
        mp[a][x.f] += x.s;
    }
}

vector <vector <int>> action;

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

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

    action.pb({c, x, mp[c][x]});
    mp[c][x]++;
}

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));
    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 24 ms 16908 KB Output is correct
2 Correct 69 ms 17936 KB Output is correct
3 Correct 63 ms 17420 KB Output is correct
4 Correct 30 ms 17424 KB Output is correct
5 Correct 50 ms 17936 KB Output is correct
6 Correct 47 ms 17176 KB Output is correct
7 Correct 32 ms 17936 KB Output is correct
8 Correct 45 ms 17996 KB Output is correct
9 Correct 44 ms 18040 KB Output is correct
10 Correct 83 ms 18420 KB Output is correct
11 Correct 59 ms 18024 KB Output is correct
12 Correct 110 ms 18700 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15884 KB Output is correct
2 Correct 23 ms 15884 KB Output is correct
3 Correct 36 ms 16140 KB Output is correct
4 Correct 24 ms 17156 KB Output is correct
5 Correct 24 ms 17676 KB Output is correct
6 Correct 40 ms 18476 KB Output is correct
7 Correct 43 ms 19280 KB Output is correct
8 Correct 52 ms 19968 KB Output is correct
9 Correct 34 ms 18696 KB Output is correct
10 Correct 73 ms 22788 KB Output is correct
11 Correct 49 ms 20916 KB Output is correct
12 Correct 64 ms 23288 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 18232 KB Output is correct
2 Correct 2179 ms 25648 KB Output is correct
3 Correct 1430 ms 25308 KB Output is correct
4 Correct 1431 ms 27412 KB Output is correct
5 Correct 2114 ms 27160 KB Output is correct
6 Correct 735 ms 19392 KB Output is correct
7 Correct 3411 ms 29052 KB Output is correct
8 Correct 3690 ms 28488 KB Output is correct
9 Correct 3398 ms 28372 KB Output is correct
10 Correct 3495 ms 28520 KB Output is correct
11 Correct 3461 ms 29136 KB Output is correct
12 Correct 3537 ms 28460 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16908 KB Output is correct
2 Correct 69 ms 17936 KB Output is correct
3 Correct 63 ms 17420 KB Output is correct
4 Correct 30 ms 17424 KB Output is correct
5 Correct 50 ms 17936 KB Output is correct
6 Correct 47 ms 17176 KB Output is correct
7 Correct 32 ms 17936 KB Output is correct
8 Correct 45 ms 17996 KB Output is correct
9 Correct 44 ms 18040 KB Output is correct
10 Correct 83 ms 18420 KB Output is correct
11 Correct 59 ms 18024 KB Output is correct
12 Correct 110 ms 18700 KB Output is correct
13 Correct 747 ms 18180 KB Output is correct
14 Correct 3683 ms 25840 KB Output is correct
15 Execution timed out 5061 ms 25716 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16908 KB Output is correct
2 Correct 69 ms 17936 KB Output is correct
3 Correct 63 ms 17420 KB Output is correct
4 Correct 30 ms 17424 KB Output is correct
5 Correct 50 ms 17936 KB Output is correct
6 Correct 47 ms 17176 KB Output is correct
7 Correct 32 ms 17936 KB Output is correct
8 Correct 45 ms 17996 KB Output is correct
9 Correct 44 ms 18040 KB Output is correct
10 Correct 83 ms 18420 KB Output is correct
11 Correct 59 ms 18024 KB Output is correct
12 Correct 110 ms 18700 KB Output is correct
13 Correct 22 ms 15884 KB Output is correct
14 Correct 23 ms 15884 KB Output is correct
15 Correct 36 ms 16140 KB Output is correct
16 Correct 24 ms 17156 KB Output is correct
17 Correct 24 ms 17676 KB Output is correct
18 Correct 40 ms 18476 KB Output is correct
19 Correct 43 ms 19280 KB Output is correct
20 Correct 52 ms 19968 KB Output is correct
21 Correct 34 ms 18696 KB Output is correct
22 Correct 73 ms 22788 KB Output is correct
23 Correct 49 ms 20916 KB Output is correct
24 Correct 64 ms 23288 KB Output is correct
25 Correct 690 ms 18232 KB Output is correct
26 Correct 2179 ms 25648 KB Output is correct
27 Correct 1430 ms 25308 KB Output is correct
28 Correct 1431 ms 27412 KB Output is correct
29 Correct 2114 ms 27160 KB Output is correct
30 Correct 735 ms 19392 KB Output is correct
31 Correct 3411 ms 29052 KB Output is correct
32 Correct 3690 ms 28488 KB Output is correct
33 Correct 3398 ms 28372 KB Output is correct
34 Correct 3495 ms 28520 KB Output is correct
35 Correct 3461 ms 29136 KB Output is correct
36 Correct 3537 ms 28460 KB Output is correct
37 Correct 747 ms 18180 KB Output is correct
38 Correct 3683 ms 25840 KB Output is correct
39 Execution timed out 5061 ms 25716 KB Time limit exceeded
40 Halted 0 ms 0 KB -