oj.uz

Submission #907820

# Submission time Handle Problem Language Result Execution time Memory
907820 2024-01-16T05:07:28 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++17
71 / 100
 5000 ms 32252 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#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 = 800;
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) {
    while (p[a])
        a = p[a];

    return 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;

    int nm = n * m;

    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 <= nm; 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 58 ms 23300 KB Output is correct
2 Correct 67 ms 24368 KB Output is correct
3 Correct 61 ms 24068 KB Output is correct
4 Correct 63 ms 23872 KB Output is correct
5 Correct 65 ms 24388 KB Output is correct
6 Correct 59 ms 23300 KB Output is correct
7 Correct 66 ms 24328 KB Output is correct
8 Correct 75 ms 24408 KB Output is correct
9 Correct 67 ms 24388 KB Output is correct
10 Correct 72 ms 24580 KB Output is correct
11 Correct 69 ms 24388 KB Output is correct
12 Correct 72 ms 25088 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 22788 KB Output is correct
2 Correct 61 ms 22788 KB Output is correct
3 Correct 63 ms 23100 KB Output is correct
4 Correct 68 ms 24828 KB Output is correct
5 Correct 70 ms 24828 KB Output is correct
6 Correct 82 ms 24316 KB Output is correct
7 Correct 99 ms 25184 KB Output is correct
8 Correct 104 ms 26320 KB Output is correct
9 Correct 105 ms 25340 KB Output is correct
10 Correct 129 ms 28412 KB Output is correct
11 Correct 113 ms 27392 KB Output is correct
12 Correct 126 ms 29360 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 24092 KB Output is correct
2 Correct 1827 ms 26496 KB Output is correct
3 Correct 1264 ms 29732 KB Output is correct
4 Correct 1308 ms 32252 KB Output is correct
5 Correct 1848 ms 29180 KB Output is correct
6 Correct 823 ms 25780 KB Output is correct
7 Correct 3916 ms 29588 KB Output is correct
8 Correct 3479 ms 29280 KB Output is correct
9 Correct 3787 ms 29288 KB Output is correct
10 Correct 3582 ms 29284 KB Output is correct
11 Correct 3229 ms 29372 KB Output is correct
12 Correct 3189 ms 29248 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 23300 KB Output is correct
2 Correct 67 ms 24368 KB Output is correct
3 Correct 61 ms 24068 KB Output is correct
4 Correct 63 ms 23872 KB Output is correct
5 Correct 65 ms 24388 KB Output is correct
6 Correct 59 ms 23300 KB Output is correct
7 Correct 66 ms 24328 KB Output is correct
8 Correct 75 ms 24408 KB Output is correct
9 Correct 67 ms 24388 KB Output is correct
10 Correct 72 ms 24580 KB Output is correct
11 Correct 69 ms 24388 KB Output is correct
12 Correct 72 ms 25088 KB Output is correct
13 Correct 712 ms 24236 KB Output is correct
14 Correct 2066 ms 26432 KB Output is correct
15 Correct 1645 ms 30204 KB Output is correct
16 Correct 1432 ms 29700 KB Output is correct
17 Correct 2049 ms 26424 KB Output is correct
18 Correct 792 ms 24580 KB Output is correct
19 Correct 1648 ms 26412 KB Output is correct
20 Correct 2015 ms 26632 KB Output is correct
21 Correct 1782 ms 26624 KB Output is correct
22 Correct 2218 ms 26692 KB Output is correct
23 Correct 2045 ms 26448 KB Output is correct
24 Correct 2548 ms 27404 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 23300 KB Output is correct
2 Correct 67 ms 24368 KB Output is correct
3 Correct 61 ms 24068 KB Output is correct
4 Correct 63 ms 23872 KB Output is correct
5 Correct 65 ms 24388 KB Output is correct
6 Correct 59 ms 23300 KB Output is correct
7 Correct 66 ms 24328 KB Output is correct
8 Correct 75 ms 24408 KB Output is correct
9 Correct 67 ms 24388 KB Output is correct
10 Correct 72 ms 24580 KB Output is correct
11 Correct 69 ms 24388 KB Output is correct
12 Correct 72 ms 25088 KB Output is correct
13 Correct 73 ms 22788 KB Output is correct
14 Correct 61 ms 22788 KB Output is correct
15 Correct 63 ms 23100 KB Output is correct
16 Correct 68 ms 24828 KB Output is correct
17 Correct 70 ms 24828 KB Output is correct
18 Correct 82 ms 24316 KB Output is correct
19 Correct 99 ms 25184 KB Output is correct
20 Correct 104 ms 26320 KB Output is correct
21 Correct 105 ms 25340 KB Output is correct
22 Correct 129 ms 28412 KB Output is correct
23 Correct 113 ms 27392 KB Output is correct
24 Correct 126 ms 29360 KB Output is correct
25 Correct 722 ms 24092 KB Output is correct
26 Correct 1827 ms 26496 KB Output is correct
27 Correct 1264 ms 29732 KB Output is correct
28 Correct 1308 ms 32252 KB Output is correct
29 Correct 1848 ms 29180 KB Output is correct
30 Correct 823 ms 25780 KB Output is correct
31 Correct 3916 ms 29588 KB Output is correct
32 Correct 3479 ms 29280 KB Output is correct
33 Correct 3787 ms 29288 KB Output is correct
34 Correct 3582 ms 29284 KB Output is correct
35 Correct 3229 ms 29372 KB Output is correct
36 Correct 3189 ms 29248 KB Output is correct
37 Correct 712 ms 24236 KB Output is correct
38 Correct 2066 ms 26432 KB Output is correct
39 Correct 1645 ms 30204 KB Output is correct
40 Correct 1432 ms 29700 KB Output is correct
41 Correct 2049 ms 26424 KB Output is correct
42 Correct 792 ms 24580 KB Output is correct
43 Correct 1648 ms 26412 KB Output is correct
44 Correct 2015 ms 26632 KB Output is correct
45 Correct 1782 ms 26624 KB Output is correct
46 Correct 2218 ms 26692 KB Output is correct
47 Correct 2045 ms 26448 KB Output is correct
48 Correct 2548 ms 27404 KB Output is correct
49 Correct 831 ms 24132 KB Output is correct
50 Correct 2278 ms 26612 KB Output is correct
51 Correct 1990 ms 30208 KB Output is correct
52 Correct 1599 ms 32172 KB Output is correct
53 Correct 2334 ms 28676 KB Output is correct
54 Correct 988 ms 25724 KB Output is correct
55 Correct 3034 ms 29100 KB Output is correct
56 Correct 4126 ms 31412 KB Output is correct
57 Correct 3109 ms 29432 KB Output is correct
58 Execution timed out 5034 ms 32216 KB Time limit exceeded
59 Halted 0 ms 0 KB -