Submission #274893

#	Time	Username	Problem	Language	Result	Execution time	Memory
274893		doowey	I want to be the very best too! (NOI17_pokemonmaster)	C++14	47 / 100	5101 ms	501464 KiB

pokemonmaster

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 50010;
const int K = N * 2;

int cur;
int n, m;

int getid(int x, int y){
    return (x - 1) * m + y;
}

int vl[K];
int par[K];
bool active[N];
vector<int> T[N];

int dir[4][2] = {{-1,0},{+1,0},{0,-1},{0,+1}};

int fin(int x){
    if(par[x]==x)return x;
    return par[x]=fin(par[x]);
}

vector<int> E[K];

void unite(int u, int v){
    u = fin(u);
    v = fin(v);
    if(u == v)
        return;
    cur ++ ;
    vl[cur] = max(vl[u], vl[v]);
    E[cur].push_back(u);
    E[cur].push_back(v);
    par[u] = cur;
    par[v] = cur;
}

const int LOG = 18;

int tin[K];
int tout[K];
int up[LOG][K];
int ti;

void dfs(int u, int pp){
    tin[u] = ++ti;
    up[0][u]=pp;
    for(int i = 1; i < LOG; i ++ )
        up[i][u]=up[i-1][up[i-1][u]];
    for(auto x : E[u]){
        dfs(x,u);
    }
    tout[u] = ti;
}

set<int> pos[N];
int L[K];
int v[K];

struct SegTree{
    struct Node{
        int val;
        int lef;
        int rig;
    };
    vector<Node> fs;
    int add_node(){
        int id = fs.size();
        fs.push_back({0,-1,-1});
        return id;
    }
    void upd(int node, int cl, int cr, int pos, int x){
        fs[node].val += x;
        if(cl == cr)
            return ;
        int mid = (cl + cr) >> 1;
        if(mid >= pos){
            if(fs[node].lef == -1){
                int nw = add_node();
                fs[node].lef = nw;
            }
            upd(fs[node].lef, cl, mid, pos, x);
        }
        else{
            if(fs[node].rig == -1){
                int nw = add_node();
                fs[node].rig = nw;
            }
            upd(fs[node].rig, mid + 1, cr, pos, x);
        }
    }
    int get(int node, int cl, int cr, int tl, int tr){
        if(node == -1 || node >= fs.size()) return 0ll;
        if(cr < tl || cl > tr) return 0ll;
        if(cl >= tl && cr <= tr){
            return fs[node].val;
        }
        int mid = (cl + cr) >> 1;
        ll ret = 0ll;
        if(fs[node].lef != -1)ret += get(fs[node].lef, cl, mid, tl, tr);
        if(fs[node].rig != -1)ret += get(fs[node].rig, mid + 1, cr, tl, tr);
        return ret;
    }
};

SegTree nd[K * 4 + 512];

void update(int node, int cl, int cr, int pos, int a, int sign){
    if(nd[node].fs.size() == 0){
        nd[node].add_node();
    }
    nd[node].upd(0, 0, cur, a, sign);
    if(cl == cr) return;
    int mid = (cl + cr) >> 1;
    if(mid >= pos)
        update(node << 1, cl, mid, pos, a, sign);
    else
        update(node << 1 | 1, mid + 1, cr, pos, a, sign);
}

int query(int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr)
        return 0;
    if(cl >= tl && cr <= tr){
        return nd[node].get(0, 0, cur, 0, tl - 1);
    }
    int mid = (cl + cr) >> 1;
    return query(node << 1, cl, mid, tl, tr) + query(node << 1 | 1, mid + 1, cr, tl, tr);
}

void delet(int id){
    update(1, 0, cur, id, L[id], -1);
    pos[v[id]].erase(id);
    auto it = pos[v[id]].lower_bound(id);
    int ix;
    if(it != pos[v[id]].end()){
        ix = *it;
        update(1, 0, cur, ix, id, -1);
        auto nx = it;
        if(nx != pos[v[id]].begin()){
            nx -- ;
            L[ix] = *nx;
            update(1, 0, cur, ix, *nx, +1);
        }
        else{
            L[ix] = 0;
            update(1, 0, cur, ix, 0, +1);
        }
    }
}

void setpos(int id, int x){
    if(x == v[id])
        return;
    if(v[id] != 0){
        delet(id);
    }
    auto it = pos[x].lower_bound(id);
    int ix;
    if(it != pos[x].end()){
        ix = *it;
        update(1, 0, cur, ix, L[ix],-1);
        update(1, 0, cur, ix, id, +1);
        L[*it] = id;
    }
    if(it != pos[x].begin()){
        it -- ;
        ix = *it;
        update(1, 0, cur, id, ix, +1);
        L[id] = ix;
    }
    else{
        update(1, 0, cur, id, 0, +1);
        L[id] = 0;
    }
    pos[x].insert(id);
    v[id] = x;
}

int main(){
    fastIO;
    int q;
    cin >> n >> m >> q;
    int sz = n * m;
    for(int i = 0 ; i < K; i ++ )
        par[i]=i;
    cur = sz;
    int l;
    vector<pii> cells;
    int ni, nj;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            cin >> l;
            cells.push_back(mp(l, getid(i, j)));
            for(int k = 0 ; k < 4; k ++ ){
                ni = i + dir[k][0];
                nj = j + dir[k][1];
                if(ni >= 1 && ni <= n && nj >= 1 && nj <= m){
                    T[getid(i,j)].push_back(getid(ni,nj));
                }
            }
        }
    }
    sort(cells.begin(), cells.end());
    for(auto p : cells){
        active[p.se]=true;
        vl[p.se] = p.fi;
        for(auto q : T[p.se]){
            if(active[q]){
                unite(p.se, q);
            }
        }
    }
    dfs(cur, cur);
    int id;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            cin >> l;
            id = getid(i,j);
            setpos(tin[id], l);
        }
    }
    int typ;
    int xi, yi;
    int cv;
    for(int qr = 0; qr < q; qr ++ ){
        cin >> typ;
        if(typ == 2){
            cin >> yi >> xi >> cv;
            id = getid(xi, yi);
            if(vl[id] > cv){
                cout << 0 << "\n";
            }
            else{
                for(int lg = LOG - 1; lg >= 0; lg -- ){
                    if(vl[up[lg][id]] <= cv){
                        id = up[lg][id];
                    }
                }
                cout << query(1, 0, cur, tin[id], tout[id]) << "\n";
            }
        }
        else{
            cin >> yi >> xi >> cv;
            id = getid(xi, yi);
            setpos(tin[id], cv);
        }
    }
    return 0;
}

Compilation message (stderr)

pokemonmaster.cpp: In member function 'int SegTree::get(int, int, int, int, int)':
pokemonmaster.cpp:106:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<SegTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         if(node == -1 || node >= fs.size()) return 0ll;
      |                          ~~~~~^~~~~~~~~~~~

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