oj.uz

Submission #907471

# Submission time Handle Problem Language Result Execution time Memory
907471 2024-01-15T17:15:57 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++17
27 / 100
 2369 ms 29216 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 = 700;
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];
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]) {
        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]]++;
            }

            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 40 ms 23052 KB Output is correct
2 Correct 47 ms 24236 KB Output is correct
3 Correct 43 ms 23812 KB Output is correct
4 Correct 42 ms 23824 KB Output is correct
5 Correct 48 ms 24072 KB Output is correct
6 Correct 38 ms 23308 KB Output is correct
7 Correct 45 ms 24320 KB Output is correct
8 Correct 54 ms 24140 KB Output is correct
9 Correct 47 ms 24068 KB Output is correct
10 Correct 53 ms 24408 KB Output is correct
11 Correct 53 ms 24076 KB Output is correct
12 Correct 55 ms 24960 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 22536 KB Output is correct
2 Correct 37 ms 22944 KB Output is correct
3 Correct 37 ms 23048 KB Output is correct
4 Correct 37 ms 23984 KB Output is correct
5 Correct 37 ms 25084 KB Output is correct
6 Correct 40 ms 24076 KB Output is correct
7 Correct 52 ms 25856 KB Output is correct
8 Correct 62 ms 26484 KB Output is correct
9 Correct 56 ms 26156 KB Output is correct
10 Correct 84 ms 28296 KB Output is correct
11 Correct 62 ms 26876 KB Output is correct
12 Correct 75 ms 29216 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 830 ms 24080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 23052 KB Output is correct
2 Correct 47 ms 24236 KB Output is correct
3 Correct 43 ms 23812 KB Output is correct
4 Correct 42 ms 23824 KB Output is correct
5 Correct 48 ms 24072 KB Output is correct
6 Correct 38 ms 23308 KB Output is correct
7 Correct 45 ms 24320 KB Output is correct
8 Correct 54 ms 24140 KB Output is correct
9 Correct 47 ms 24068 KB Output is correct
10 Correct 53 ms 24408 KB Output is correct
11 Correct 53 ms 24076 KB Output is correct
12 Correct 55 ms 24960 KB Output is correct
13 Correct 842 ms 23544 KB Output is correct
14 Correct 2369 ms 26036 KB Output is correct
15 Incorrect 1968 ms 29116 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 23052 KB Output is correct
2 Correct 47 ms 24236 KB Output is correct
3 Correct 43 ms 23812 KB Output is correct
4 Correct 42 ms 23824 KB Output is correct
5 Correct 48 ms 24072 KB Output is correct
6 Correct 38 ms 23308 KB Output is correct
7 Correct 45 ms 24320 KB Output is correct
8 Correct 54 ms 24140 KB Output is correct
9 Correct 47 ms 24068 KB Output is correct
10 Correct 53 ms 24408 KB Output is correct
11 Correct 53 ms 24076 KB Output is correct
12 Correct 55 ms 24960 KB Output is correct
13 Correct 34 ms 22536 KB Output is correct
14 Correct 37 ms 22944 KB Output is correct
15 Correct 37 ms 23048 KB Output is correct
16 Correct 37 ms 23984 KB Output is correct
17 Correct 37 ms 25084 KB Output is correct
18 Correct 40 ms 24076 KB Output is correct
19 Correct 52 ms 25856 KB Output is correct
20 Correct 62 ms 26484 KB Output is correct
21 Correct 56 ms 26156 KB Output is correct
22 Correct 84 ms 28296 KB Output is correct
23 Correct 62 ms 26876 KB Output is correct
24 Correct 75 ms 29216 KB Output is correct
25 Incorrect 830 ms 24080 KB Output isn't correct
26 Halted 0 ms 0 KB -