oj.uz

Submission #915952

# Submission time Handle Problem Language Result Execution time Memory
915952 2024-01-25T01:30:32 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++14
71 / 100
 5000 ms 35148 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 {
                int id = cov(x[j], y[j]);
                if (change[id] == 0) {
                    up.pb(id);
                }
                change[id] = 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({t, P[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]]++;
                sz[j] = 1;
            } else {
                sz[j] = 0;
                cc[j] = 0;
            }
 
            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[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 66 ms 23848 KB Output is correct
2 Correct 73 ms 24832 KB Output is correct
3 Correct 70 ms 24580 KB Output is correct
4 Correct 68 ms 24356 KB Output is correct
5 Correct 77 ms 24876 KB Output is correct
6 Correct 66 ms 23808 KB Output is correct
7 Correct 72 ms 24832 KB Output is correct
8 Correct 75 ms 24876 KB Output is correct
9 Correct 75 ms 24848 KB Output is correct
10 Correct 84 ms 25336 KB Output is correct
11 Correct 76 ms 24840 KB Output is correct
12 Correct 78 ms 25600 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 23556 KB Output is correct
2 Correct 71 ms 23468 KB Output is correct
3 Correct 71 ms 23864 KB Output is correct
4 Correct 77 ms 24828 KB Output is correct
5 Correct 79 ms 24832 KB Output is correct
6 Correct 80 ms 24828 KB Output is correct
7 Correct 115 ms 26776 KB Output is correct
8 Correct 115 ms 27156 KB Output is correct
9 Correct 105 ms 26180 KB Output is correct
10 Correct 132 ms 29464 KB Output is correct
11 Correct 115 ms 27704 KB Output is correct
12 Correct 126 ms 30188 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 26560 KB Output is correct
2 Correct 1753 ms 28688 KB Output is correct
3 Correct 1250 ms 31608 KB Output is correct
4 Correct 1382 ms 33276 KB Output is correct
5 Correct 1821 ms 29948 KB Output is correct
6 Correct 734 ms 27620 KB Output is correct
7 Correct 2875 ms 31284 KB Output is correct
8 Correct 3081 ms 31304 KB Output is correct
9 Correct 2946 ms 31740 KB Output is correct
10 Correct 3189 ms 31568 KB Output is correct
11 Correct 2913 ms 31296 KB Output is correct
12 Correct 2907 ms 31488 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23848 KB Output is correct
2 Correct 73 ms 24832 KB Output is correct
3 Correct 70 ms 24580 KB Output is correct
4 Correct 68 ms 24356 KB Output is correct
5 Correct 77 ms 24876 KB Output is correct
6 Correct 66 ms 23808 KB Output is correct
7 Correct 72 ms 24832 KB Output is correct
8 Correct 75 ms 24876 KB Output is correct
9 Correct 75 ms 24848 KB Output is correct
10 Correct 84 ms 25336 KB Output is correct
11 Correct 76 ms 24840 KB Output is correct
12 Correct 78 ms 25600 KB Output is correct
13 Correct 696 ms 26096 KB Output is correct
14 Correct 1990 ms 28676 KB Output is correct
15 Correct 1610 ms 32256 KB Output is correct
16 Correct 1324 ms 31744 KB Output is correct
17 Correct 1998 ms 28676 KB Output is correct
18 Correct 820 ms 26568 KB Output is correct
19 Correct 1653 ms 28416 KB Output is correct
20 Correct 1987 ms 28524 KB Output is correct
21 Correct 1767 ms 28420 KB Output is correct
22 Correct 2158 ms 29036 KB Output is correct
23 Correct 2028 ms 28548 KB Output is correct
24 Correct 2508 ms 29276 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23848 KB Output is correct
2 Correct 73 ms 24832 KB Output is correct
3 Correct 70 ms 24580 KB Output is correct
4 Correct 68 ms 24356 KB Output is correct
5 Correct 77 ms 24876 KB Output is correct
6 Correct 66 ms 23808 KB Output is correct
7 Correct 72 ms 24832 KB Output is correct
8 Correct 75 ms 24876 KB Output is correct
9 Correct 75 ms 24848 KB Output is correct
10 Correct 84 ms 25336 KB Output is correct
11 Correct 76 ms 24840 KB Output is correct
12 Correct 78 ms 25600 KB Output is correct
13 Correct 78 ms 23556 KB Output is correct
14 Correct 71 ms 23468 KB Output is correct
15 Correct 71 ms 23864 KB Output is correct
16 Correct 77 ms 24828 KB Output is correct
17 Correct 79 ms 24832 KB Output is correct
18 Correct 80 ms 24828 KB Output is correct
19 Correct 115 ms 26776 KB Output is correct
20 Correct 115 ms 27156 KB Output is correct
21 Correct 105 ms 26180 KB Output is correct
22 Correct 132 ms 29464 KB Output is correct
23 Correct 115 ms 27704 KB Output is correct
24 Correct 126 ms 30188 KB Output is correct
25 Correct 711 ms 26560 KB Output is correct
26 Correct 1753 ms 28688 KB Output is correct
27 Correct 1250 ms 31608 KB Output is correct
28 Correct 1382 ms 33276 KB Output is correct
29 Correct 1821 ms 29948 KB Output is correct
30 Correct 734 ms 27620 KB Output is correct
31 Correct 2875 ms 31284 KB Output is correct
32 Correct 3081 ms 31304 KB Output is correct
33 Correct 2946 ms 31740 KB Output is correct
34 Correct 3189 ms 31568 KB Output is correct
35 Correct 2913 ms 31296 KB Output is correct
36 Correct 2907 ms 31488 KB Output is correct
37 Correct 696 ms 26096 KB Output is correct
38 Correct 1990 ms 28676 KB Output is correct
39 Correct 1610 ms 32256 KB Output is correct
40 Correct 1324 ms 31744 KB Output is correct
41 Correct 1998 ms 28676 KB Output is correct
42 Correct 820 ms 26568 KB Output is correct
43 Correct 1653 ms 28416 KB Output is correct
44 Correct 1987 ms 28524 KB Output is correct
45 Correct 1767 ms 28420 KB Output is correct
46 Correct 2158 ms 29036 KB Output is correct
47 Correct 2028 ms 28548 KB Output is correct
48 Correct 2508 ms 29276 KB Output is correct
49 Correct 796 ms 27036 KB Output is correct
50 Correct 2234 ms 29188 KB Output is correct
51 Correct 1824 ms 32772 KB Output is correct
52 Correct 1448 ms 33300 KB Output is correct
53 Correct 2160 ms 31360 KB Output is correct
54 Correct 952 ms 28924 KB Output is correct
55 Correct 2522 ms 31688 KB Output is correct
56 Correct 4080 ms 33272 KB Output is correct
57 Correct 3062 ms 32252 KB Output is correct
58 Execution timed out 5007 ms 35148 KB Time limit exceeded
59 Halted 0 ms 0 KB -