제출 #1234824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234824		Geforgs	I want to be the very best too! (NOI17_pokemonmaster)	C++20	47 / 100	1289 ms	589824 KiB

pokemonmaster

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

const ll dim = 20;

struct Node{
    ll left=-1, right=-1, sum=0;
};

pair<ll, ll> get(pair<ll, ll> x, vector<vector<pair<ll, ll>>>& parent){
    if(parent[x.first][x.second] == x) return x;
    return parent[x.first][x.second] = get(parent[x.first][x.second], parent);
}

void unite(pair<ll, ll> x, pair<ll, ll> y, vector<vector<pair<ll, ll>>>& parent, vector<vector<vector<pair<ll, ll>>>>& children){
    x = get(x, parent);
    y = get(y, parent);
    if(x == y) return;
    parent[y.first][y.second] = x;
    children[x.first][x.second].pb(y);
}

void DFS(pair<ll, ll> id, pair<ll, ll> last, ll& time, vector<vector<vector<pair<ll, ll>>>>& children, vector<vector<vector<pair<ll, ll>>>>& up, vector<vector<ll>>& tin, vector<vector<ll>>& tout){
    tin[id.first][id.second] = ++time;
    up[id.first][id.second][0] = last;
    for(int i=1;i<dim;++i){
        up[id.first][id.second][i] = up[up[id.first][id.second][i-1].first][up[id.first][id.second][i-1].second][i-1];
    }
    for(auto el: children[id.first][id.second]){
        DFS(el, id, time, children, up, tin, tout);
    }
    tout[id.first][id.second] = time;
}

void add(ll id, ll l, ll r, ll pos, ll val, vector<Node>& nodes){
    if(id == -1) return;
    nodes[id].sum += val;
    if(l == r) return;
    ll m=(l+r)/2;
    if(pos <= m){
        if(nodes[id].left == -1){
            nodes[id].left = nodes.size();
            nodes.pb(Node());
        }
        add(nodes[id].left, l, m, pos, val, nodes);
    }else{
        if(nodes[id].right == -1){
            nodes[id].right = nodes.size();
            nodes.pb(Node());
        }
        add(nodes[id].right, m+1, r, pos, val, nodes);
    }
}

ll get(ll id, ll l, ll r, ll x, vector<Node>& nodes){
    if(l == r) return 0;
    ll m=(l+r)/2;
    if(x <= m){
        ll res=0;
        if(nodes[id].left != -1){
            res += get(nodes[id].left, l, m, x, nodes);
        }
        if(nodes[id].right != -1){
            res += nodes[nodes[id].right].sum;
        }
        return res;
    }
    ll res=0;
    if(nodes[id].right != -1){
        res += get(nodes[id].right, m+1, r, x, nodes);
    }
    return res;
}

void add(ll id, ll l, ll r, ll x, ll pos, ll val, vector<ll>& c, vector<Node>& nodes){
    add(c[id], 0, 1e6, pos, val, nodes);
    if(l == r) return;
    ll m=(l+r)/2;
    if(x <= m) add(2*id, l, m, x, pos, val, c, nodes);
    else add(2*id + 1, m+1, r, x, pos, val, c, nodes);
}

ll get(ll id, ll l, ll r, ll tl, ll tr, ll x, vector<ll>& c, vector<Node>& nodes){
    if(r < tl or tr < l) return 0;
    if(tl <= l and r <= tr){
        return get(c[id], 0, 1e6, x, nodes);
    }
    ll m=(l+r)/2;
    return get(2*id, l, m, tl, tr, x, c, nodes) + get(2*id+1, m+1, r, tl, tr, x, c, nodes);
}

pair<ll, ll> get(pair<ll, ll> x, ll val, vector<vector<ll>>& L, vector<vector<vector<pair<ll, ll>>>>& up){
    for(int i=dim-1;i>=0;--i){
        if(L[up[x.first][x.second][i].first][up[x.first][x.second][i].second] <= val){
            x = up[x.first][x.second][i];
        }
    }
    return x;
}

void solve(){
    ll n, m, q, i, j, time=-1, x, y, val, type, pos;
    pair<ll, ll> last;
    cin>>n>>m>>q;
    vector<vector<ll>> L(n, vector<ll>(m));
    vector<vector<ll>> P(n, vector<ll>(m));
    vector<vector<pair<ll, ll>>> parent(n, vector<pair<ll, ll>>(m));
    vector<vector<vector<pair<ll, ll>>>> children(n, vector<vector<pair<ll, ll>>>(m));
    vector<vector<vector<pair<ll, ll>>>> up(n, vector<vector<pair<ll, ll>>>(m, vector<pair<ll, ll>>(dim)));
    map<ll, vector<pair<ll, ll>>> level;
    map<ll, set<ll>> next;
    vector<vector<ll>> tin(n, vector<ll>(m));
    vector<vector<ll>> tout(n, vector<ll>(m));
    for(i=0;i<n;++i){
        for(j=0;j<m;++j){
            cin>>L[i][j];
            level[L[i][j]].pb({i, j});
            parent[i][j] = {i, j};
        }
    }
    for(i=0;i<n;++i){
        for(j=0;j<m;++j){
            cin>>P[i][j];
            next[P[i][j]].insert(1e6);
        }
    }
    for(auto& l: level){
        for(auto el: l.second){
            if(el.first > 0 and L[el.first-1][el.second] <= L[el.first][el.second]){
                unite(el, {el.first-1, el.second}, parent, children);
            }
            if(el.first < n-1 and L[el.first+1][el.second] <= L[el.first][el.second]){
                unite(el, {el.first+1, el.second}, parent, children);
            }
            if(el.second > 0 and L[el.first][el.second-1] <= L[el.first][el.second]){
                unite(el, {el.first, el.second-1}, parent, children);
            }
            if(el.second < m-1 and L[el.first][el.second+1] <= L[el.first][el.second]){
                unite(el, {el.first, el.second+1}, parent, children);
            }
            last = el;
        }
    }
    DFS(last, last, time, children, up, tin, tout);
    ++time;
    vector<ll> a(time);
    vector<ll> b(time);
    vector<ll> c(4*time);
    vector<Node> nodes(4*time);
    for(i=0;i<4*time;++i){
        c[i] = i;
    }
    for(i=0;i<n;++i){
        for(j=0;j<m;++j){
            a[tin[i][j]] = P[i][j];
        }
    }
    for(i=time-1;i>=0;--i){
        b[i] = *next[a[i]].begin();
        next[a[i]].insert(i);
        add(1, 0, time-1, i, b[i], 1, c, nodes);
    }
    for(i=0;i<q;++i){
        cin>>type;
        if(type == 2){
            cin>>x>>y>>val;
            swap(x, y);
            --x;
            --y;
            if(L[x][y] > val){
                cout<<0<<endl;
                continue;
            }
            auto p = get({x, y}, val, L, up);
            x = p.first;
            y = p.second;
            cout<<get(1, 0, time-1, tin[x][y], tout[x][y], tout[x][y], c, nodes)<<endl;
        }else{
            cin>>x>>y>>val;
            swap(x, y);
            --x;
            --y;
            pos = tin[x][y];
            add(1, 0, time-1, pos, b[pos], -1, c, nodes);
            auto it = next[a[pos]].find(pos);
            if(it != next[a[pos]].begin()){
                auto it2 = it;
                auto it3 = it;
                --it2;
                ++it3;
                add(1, 0, time-1, *it2, *it, -1, c, nodes);
                add(1, 0, time-1, *it2, *it3, 1, c, nodes);
                b[*it2] = *it3;
            }
            next[a[pos]].erase(it);
            a[pos] = val;
            next[a[pos]].insert(pos);
            next[a[pos]].insert(1e6);
            it = next[a[pos]].find(pos);
            if(it != next[a[pos]].begin()){
                auto it2 = it;
                auto it3 = it;
                --it2;
                ++it3;
                add(1, 0, time-1, *it2, *it, 1, c, nodes);
                add(1, 0, time-1, *it2, *it3, -1, c, nodes);
                b[*it2] = *it;
            }
            b[pos] = *(++it);
            add(1, 0, time-1, pos, b[pos], 1, c, nodes);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 29