oj.uz

Submission #899477

# Submission time Handle Problem Language Result Execution time Memory
899477 2024-01-06T09:18:16 Z Cookie I want to be the very best too! (NOI17_pokemonmaster) C++14
100 / 100
 4338 ms 90552 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, 0, -1, 0};
const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7;
const int mxn = 5e4 + 69, mxq = 1e5 + 5, sq = 500, mxv = 2e7 + 5;
//const int base = (1 <<18);
const int inf = 1e9 + 5, neg = -69420;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int x[9] = {0, 1, 1, -1, -1, 2, -2, 2, -2};
//const inty[9] = {0, 2, -2, 2, -2, 1, 1, -1, -1};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
int r, c, q;
vt<vt<int>>a, colour;
int toa[mxn + 1];
bool cmp(pii ca, pii cb){
    return(a[ca.fi][ca.se] < a[cb.fi][cb.se]);
}
int pa[mxn + 1], tin[mxn + 1], tout[mxn + 1], tt = 0, tonode[mxn + 1], up[mxn + 1][17], rp[mxn + 1], toc[mxn + 1];
vt<int>adj[mxn + 1];
int fp(int u){
    if(pa[u] < 0)return(u);
    return((pa[u] = fp(pa[u])));
}
bool unon(int u, int v){
    u = fp(u); v = fp(v);
    if(u == v)return(0);
    pa[u] += pa[v]; pa[v] = u;
    return(1);
}
void dfs(int s){
    tin[s] = ++tt; tonode[tt] = s;
    for(auto i: adj[s]){
        dfs(i);
    }
    tout[s] = tt;
}

set<int>co[mxn + 1];
ordered_set st[4 * mxn + 1];
void build(int nd, int l, int r){
    if(l == r){
        st[nd].insert(mpp(rp[l], l));
        return;
    }
    int mid = (l + r) >> 1;
    build(nd << 1, l, mid); build(nd << 1 | 1, mid + 1, r);
    for(int i = l; i <= r; i++)st[nd].insert(mpp(rp[i], i));
}
void upd(int nd, int l, int r, int id, int v){
    st[nd].erase(mpp(rp[id], id)); st[nd].insert(mpp(v, id));
    if(l == r)return;
    int mid = (l + r) >> 1;
    if(id <= mid)upd(nd << 1, l, mid, id, v);
    else upd(nd << 1 | 1, mid + 1, r, id, v);
}
int get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r){
        int cntless = st[nd].order_of_key(mpp(qr, inf));
        //for(auto i: st[nd])cout << i.fi << " " << i.se << "\n";
        return(r - l + 1 - cntless);
    }
    int mid = (l + r) >> 1;
    return(get(nd << 1, l, mid, ql, qr) + get(nd << 1 | 1, mid + 1, r, ql, qr));
}
void rem(int idc, int pos){
    auto it = co[idc].lower_bound(pos);
    if(it != co[idc].begin()){
        auto lw = prev(it), hg = next(it);
        if(hg == co[idc].end()){
            upd(1, 1, r * c, *lw, r * c + 1); 
			rp[*lw] = r * c + 1;
        }else{
            upd(1, 1, r * c, *lw, *hg); 
			rp[*lw] = *hg;
        }
    }
    co[idc].erase(pos);
}
void add(int idc, int pos){
    auto it = co[idc].lower_bound(pos);
    if(it != co[idc].end()){
        upd(1, 1, r * c, pos, *it); 
		rp[pos] = *it;
    }else{
        upd(1, 1, r * c, pos, r * c + 1); 
		rp[pos] = r * c + 1;
    }
    if(it != co[idc].begin()){
        auto lg = prev(it);
        upd(1, 1, r * c, *lg, pos); 
		rp[*lg] = pos;
    }
    co[idc].insert(pos);
}
int coef(int px, int py){
    return((px - 1) * c + py);
}
bool inside(int px, int py){
    return(px >= 1 && py >= 1 && px <= r && py <= c);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("COLLEGE.INP", "r", stdin);
    //freopen("COLLEGE.OUT", "w", stdout);
    cin >> r >> c >> q;
    for(int i = 1; i <= r * c; i++)pa[i] = -1;
    vt<pii>comp;
    a.resize(r + 1, vt<int>(c + 1)); colour.resize(r + 1, vt<int>(c + 1));
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            cin >> a[i][j]; comp.pb(mpp(i, j));  toa[coef(i, j)] = a[i][j];
        }
    }
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){

            cin >> toc[coef(i, j)];
        }
    }

    sort(ALL(comp), cmp);
    for(auto [px, py]: comp){
        int u = coef(px, py);
        forr(i, 0, 4){
            int nwx = px + x[i], nwy = py + y[i];
            if(inside(nwx, nwy) && a[nwx][nwy] < a[px][py]){

                int v = fp(coef(nwx, nwy));
                if(unon(u, v)){
                    adj[u].pb(v); up[v][0] = u;
                }
            }
        }
    }


    int root = fp(1); up[root][0] = root;
    //for(int i = 1; i <= r * c; i++)cout << up[i][0] << " ";
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= r * c; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
            //cout << up[j][i] << " ";
        }
    }

    dfs(root);
    for(int i = r * c; i >= 1; i--){
        int u = tonode[i];
        if(co[toc[u]].empty()){
            rp[i] = r * c + 1;
        }else{
            rp[i] = *co[toc[u]].begin();
        }
        //cout << u << " " << rp[i] << "\n";
        co[toc[u]].insert(i);
    }
    build(1, 1, r * c);
    //cout << rp[4] << " " << rp[5] << " ";

    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int px, py, p; cin >> px >> py >> p; swap(px, py);
            int u = coef(px, py);
            rem(toc[u], tin[u]); toc[u] = p; add(toc[u], tin[u]);
        }else{
            int px, py, l; cin >> px >> py >> l; swap(px, py);
            int u = coef(px, py);
            if(toa[u] > l){
                //cout << "aa";
                cout << 0 << "\n";
            }else{
                for(int i = 16; i >= 0; i--){
                    if(toa[up[u][i]] <= l){
                        u = up[u][i];
                    }
                }

                cout << get(1, 1, r * c, tin[u], tout[u]) << "\n";
            }
        }
    }

    return(0);
}
/*
1 5 1
1 2 3 4 5
1 1 2 1 2
2 2 1 2
2 1 1 4
2 4 1 3
1 3 1 1
2 3 1 4
*/

Compilation message

pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:147:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |     for(auto [px, py]: comp){
      |              ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 86660 KB Output is correct
2 Correct 206 ms 86664 KB Output is correct
3 Correct 254 ms 86756 KB Output is correct
4 Correct 196 ms 86900 KB Output is correct
5 Correct 203 ms 86828 KB Output is correct
6 Correct 200 ms 86916 KB Output is correct
7 Correct 228 ms 86648 KB Output is correct
8 Correct 214 ms 86924 KB Output is correct
9 Correct 180 ms 86920 KB Output is correct
10 Correct 219 ms 86808 KB Output is correct
11 Correct 223 ms 86740 KB Output is correct
12 Correct 217 ms 86692 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 86516 KB Output is correct
2 Correct 188 ms 86408 KB Output is correct
3 Correct 218 ms 86344 KB Output is correct
4 Correct 161 ms 88080 KB Output is correct
5 Correct 165 ms 88588 KB Output is correct
6 Correct 174 ms 86732 KB Output is correct
7 Correct 237 ms 85452 KB Output is correct
8 Correct 192 ms 85444 KB Output is correct
9 Correct 182 ms 85452 KB Output is correct
10 Correct 217 ms 85456 KB Output is correct
11 Correct 206 ms 85452 KB Output is correct
12 Correct 220 ms 85364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 88212 KB Output is correct
2 Correct 1603 ms 88016 KB Output is correct
3 Correct 2247 ms 87668 KB Output is correct
4 Correct 2112 ms 89416 KB Output is correct
5 Correct 1504 ms 89976 KB Output is correct
6 Correct 540 ms 88832 KB Output is correct
7 Correct 1544 ms 86820 KB Output is correct
8 Correct 1555 ms 87036 KB Output is correct
9 Correct 1562 ms 87096 KB Output is correct
10 Correct 1530 ms 87076 KB Output is correct
11 Correct 1522 ms 86856 KB Output is correct
12 Correct 1575 ms 86892 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 86660 KB Output is correct
2 Correct 206 ms 86664 KB Output is correct
3 Correct 254 ms 86756 KB Output is correct
4 Correct 196 ms 86900 KB Output is correct
5 Correct 203 ms 86828 KB Output is correct
6 Correct 200 ms 86916 KB Output is correct
7 Correct 228 ms 86648 KB Output is correct
8 Correct 214 ms 86924 KB Output is correct
9 Correct 180 ms 86920 KB Output is correct
10 Correct 219 ms 86808 KB Output is correct
11 Correct 223 ms 86740 KB Output is correct
12 Correct 217 ms 86692 KB Output is correct
13 Correct 544 ms 88416 KB Output is correct
14 Correct 2420 ms 88560 KB Output is correct
15 Correct 4279 ms 88480 KB Output is correct
16 Correct 2390 ms 88376 KB Output is correct
17 Correct 2350 ms 88808 KB Output is correct
18 Correct 761 ms 88936 KB Output is correct
19 Correct 1467 ms 88400 KB Output is correct
20 Correct 2158 ms 88592 KB Output is correct
21 Correct 1499 ms 88492 KB Output is correct
22 Correct 2821 ms 88440 KB Output is correct
23 Correct 2459 ms 88592 KB Output is correct
24 Correct 2321 ms 88788 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 86660 KB Output is correct
2 Correct 206 ms 86664 KB Output is correct
3 Correct 254 ms 86756 KB Output is correct
4 Correct 196 ms 86900 KB Output is correct
5 Correct 203 ms 86828 KB Output is correct
6 Correct 200 ms 86916 KB Output is correct
7 Correct 228 ms 86648 KB Output is correct
8 Correct 214 ms 86924 KB Output is correct
9 Correct 180 ms 86920 KB Output is correct
10 Correct 219 ms 86808 KB Output is correct
11 Correct 223 ms 86740 KB Output is correct
12 Correct 217 ms 86692 KB Output is correct
13 Correct 185 ms 86516 KB Output is correct
14 Correct 188 ms 86408 KB Output is correct
15 Correct 218 ms 86344 KB Output is correct
16 Correct 161 ms 88080 KB Output is correct
17 Correct 165 ms 88588 KB Output is correct
18 Correct 174 ms 86732 KB Output is correct
19 Correct 237 ms 85452 KB Output is correct
20 Correct 192 ms 85444 KB Output is correct
21 Correct 182 ms 85452 KB Output is correct
22 Correct 217 ms 85456 KB Output is correct
23 Correct 206 ms 85452 KB Output is correct
24 Correct 220 ms 85364 KB Output is correct
25 Correct 621 ms 88212 KB Output is correct
26 Correct 1603 ms 88016 KB Output is correct
27 Correct 2247 ms 87668 KB Output is correct
28 Correct 2112 ms 89416 KB Output is correct
29 Correct 1504 ms 89976 KB Output is correct
30 Correct 540 ms 88832 KB Output is correct
31 Correct 1544 ms 86820 KB Output is correct
32 Correct 1555 ms 87036 KB Output is correct
33 Correct 1562 ms 87096 KB Output is correct
34 Correct 1530 ms 87076 KB Output is correct
35 Correct 1522 ms 86856 KB Output is correct
36 Correct 1575 ms 86892 KB Output is correct
37 Correct 544 ms 88416 KB Output is correct
38 Correct 2420 ms 88560 KB Output is correct
39 Correct 4279 ms 88480 KB Output is correct
40 Correct 2390 ms 88376 KB Output is correct
41 Correct 2350 ms 88808 KB Output is correct
42 Correct 761 ms 88936 KB Output is correct
43 Correct 1467 ms 88400 KB Output is correct
44 Correct 2158 ms 88592 KB Output is correct
45 Correct 1499 ms 88492 KB Output is correct
46 Correct 2821 ms 88440 KB Output is correct
47 Correct 2459 ms 88592 KB Output is correct
48 Correct 2321 ms 88788 KB Output is correct
49 Correct 589 ms 88468 KB Output is correct
50 Correct 2433 ms 88216 KB Output is correct
51 Correct 4338 ms 88392 KB Output is correct
52 Correct 2354 ms 89720 KB Output is correct
53 Correct 2247 ms 90552 KB Output is correct
54 Correct 793 ms 89020 KB Output is correct
55 Correct 1551 ms 87192 KB Output is correct
56 Correct 2175 ms 87184 KB Output is correct
57 Correct 1532 ms 87096 KB Output is correct
58 Correct 2795 ms 87244 KB Output is correct
59 Correct 2550 ms 87316 KB Output is correct
60 Correct 2523 ms 87388 KB Output is correct