oj.uz

Submission #907847

# Submission time Handle Problem Language Result Execution time Memory
907847 2024-01-16T05:20:52 Z LOLOLO I want to be the very best too! (NOI17_pokemonmaster) C++17
27 / 100
 5000 ms 29988 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(mp[a]) < sz(mp[b]))
        swap(a, 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]]++;
            } else {
                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 61 ms 23300 KB Output is correct
2 Correct 70 ms 24456 KB Output is correct
3 Correct 69 ms 24068 KB Output is correct
4 Correct 76 ms 23868 KB Output is correct
5 Correct 68 ms 24368 KB Output is correct
6 Correct 63 ms 23304 KB Output is correct
7 Correct 4613 ms 24380 KB Output is correct
8 Correct 75 ms 24392 KB Output is correct
9 Correct 83 ms 24372 KB Output is correct
10 Correct 70 ms 24628 KB Output is correct
11 Correct 83 ms 24320 KB Output is correct
12 Correct 77 ms 25180 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 22784 KB Output is correct
2 Correct 66 ms 22788 KB Output is correct
3 Correct 86 ms 23112 KB Output is correct
4 Correct 71 ms 25212 KB Output is correct
5 Correct 76 ms 24832 KB Output is correct
6 Correct 78 ms 25376 KB Output is correct
7 Correct 1194 ms 25260 KB Output is correct
8 Correct 113 ms 26368 KB Output is correct
9 Correct 104 ms 25548 KB Output is correct
10 Correct 153 ms 28372 KB Output is correct
11 Correct 140 ms 27076 KB Output is correct
12 Correct 127 ms 29492 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5011 ms 24068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 23300 KB Output is correct
2 Correct 70 ms 24456 KB Output is correct
3 Correct 69 ms 24068 KB Output is correct
4 Correct 76 ms 23868 KB Output is correct
5 Correct 68 ms 24368 KB Output is correct
6 Correct 63 ms 23304 KB Output is correct
7 Correct 4613 ms 24380 KB Output is correct
8 Correct 75 ms 24392 KB Output is correct
9 Correct 83 ms 24372 KB Output is correct
10 Correct 70 ms 24628 KB Output is correct
11 Correct 83 ms 24320 KB Output is correct
12 Correct 77 ms 25180 KB Output is correct
13 Correct 793 ms 24104 KB Output is correct
14 Correct 2381 ms 26436 KB Output is correct
15 Correct 2184 ms 29988 KB Output is correct
16 Correct 1729 ms 29652 KB Output is correct
17 Correct 1992 ms 26552 KB Output is correct
18 Correct 828 ms 24580 KB Output is correct
19 Execution timed out 5057 ms 25572 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 23300 KB Output is correct
2 Correct 70 ms 24456 KB Output is correct
3 Correct 69 ms 24068 KB Output is correct
4 Correct 76 ms 23868 KB Output is correct
5 Correct 68 ms 24368 KB Output is correct
6 Correct 63 ms 23304 KB Output is correct
7 Correct 4613 ms 24380 KB Output is correct
8 Correct 75 ms 24392 KB Output is correct
9 Correct 83 ms 24372 KB Output is correct
10 Correct 70 ms 24628 KB Output is correct
11 Correct 83 ms 24320 KB Output is correct
12 Correct 77 ms 25180 KB Output is correct
13 Correct 62 ms 22784 KB Output is correct
14 Correct 66 ms 22788 KB Output is correct
15 Correct 86 ms 23112 KB Output is correct
16 Correct 71 ms 25212 KB Output is correct
17 Correct 76 ms 24832 KB Output is correct
18 Correct 78 ms 25376 KB Output is correct
19 Correct 1194 ms 25260 KB Output is correct
20 Correct 113 ms 26368 KB Output is correct
21 Correct 104 ms 25548 KB Output is correct
22 Correct 153 ms 28372 KB Output is correct
23 Correct 140 ms 27076 KB Output is correct
24 Correct 127 ms 29492 KB Output is correct
25 Execution timed out 5011 ms 24068 KB Time limit exceeded
26 Halted 0 ms 0 KB -