Submission #899477

#	Time	Username	Problem	Language	Result	Execution time	Memory
899477		Cookie	I want to be the very best too! (NOI17_pokemonmaster)	C++14	100 / 100	4338 ms	90552 KiB

pokemonmaster

#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 (stderr)

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 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 29 / 29