oj.uz

Submission #274893

# Submission time Handle Problem Language Result Execution time Memory
274893 2020-08-19T20:58:56 Z doowey I want to be the very best too! (NOI17_pokemonmaster) C++14
47 / 100
 5000 ms 501464 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 171228 KB Output is correct
2 Correct 715 ms 184772 KB Output is correct
3 Correct 874 ms 204140 KB Output is correct
4 Correct 647 ms 171484 KB Output is correct
5 Correct 702 ms 183912 KB Output is correct
6 Correct 792 ms 199364 KB Output is correct
7 Correct 627 ms 170332 KB Output is correct
8 Correct 686 ms 180084 KB Output is correct
9 Correct 632 ms 170708 KB Output is correct
10 Correct 820 ms 201564 KB Output is correct
11 Correct 756 ms 189536 KB Output is correct
12 Correct 742 ms 179048 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 161756 KB Output is correct
2 Correct 653 ms 174932 KB Output is correct
3 Correct 747 ms 191448 KB Output is correct
4 Correct 641 ms 162392 KB Output is correct
5 Correct 752 ms 189144 KB Output is correct
6 Correct 913 ms 211760 KB Output is correct
7 Correct 895 ms 129628 KB Output is correct
8 Correct 1244 ms 179396 KB Output is correct
9 Correct 1000 ms 137048 KB Output is correct
10 Correct 1343 ms 224092 KB Output is correct
11 Correct 1290 ms 205144 KB Output is correct
12 Correct 726 ms 171100 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 164064 KB Output is correct
2 Correct 1602 ms 169264 KB Output is correct
3 Correct 1795 ms 170528 KB Output is correct
4 Correct 1949 ms 174596 KB Output is correct
5 Correct 1568 ms 172936 KB Output is correct
6 Correct 1027 ms 160464 KB Output is correct
7 Correct 1952 ms 144672 KB Output is correct
8 Correct 1958 ms 144604 KB Output is correct
9 Correct 2105 ms 144828 KB Output is correct
10 Correct 1972 ms 144584 KB Output is correct
11 Correct 1926 ms 144344 KB Output is correct
12 Correct 1891 ms 144496 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 171228 KB Output is correct
2 Correct 715 ms 184772 KB Output is correct
3 Correct 874 ms 204140 KB Output is correct
4 Correct 647 ms 171484 KB Output is correct
5 Correct 702 ms 183912 KB Output is correct
6 Correct 792 ms 199364 KB Output is correct
7 Correct 627 ms 170332 KB Output is correct
8 Correct 686 ms 180084 KB Output is correct
9 Correct 632 ms 170708 KB Output is correct
10 Correct 820 ms 201564 KB Output is correct
11 Correct 756 ms 189536 KB Output is correct
12 Correct 742 ms 179048 KB Output is correct
13 Correct 1125 ms 176012 KB Output is correct
14 Correct 3302 ms 300740 KB Output is correct
15 Execution timed out 5101 ms 501464 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 171228 KB Output is correct
2 Correct 715 ms 184772 KB Output is correct
3 Correct 874 ms 204140 KB Output is correct
4 Correct 647 ms 171484 KB Output is correct
5 Correct 702 ms 183912 KB Output is correct
6 Correct 792 ms 199364 KB Output is correct
7 Correct 627 ms 170332 KB Output is correct
8 Correct 686 ms 180084 KB Output is correct
9 Correct 632 ms 170708 KB Output is correct
10 Correct 820 ms 201564 KB Output is correct
11 Correct 756 ms 189536 KB Output is correct
12 Correct 742 ms 179048 KB Output is correct
13 Correct 643 ms 161756 KB Output is correct
14 Correct 653 ms 174932 KB Output is correct
15 Correct 747 ms 191448 KB Output is correct
16 Correct 641 ms 162392 KB Output is correct
17 Correct 752 ms 189144 KB Output is correct
18 Correct 913 ms 211760 KB Output is correct
19 Correct 895 ms 129628 KB Output is correct
20 Correct 1244 ms 179396 KB Output is correct
21 Correct 1000 ms 137048 KB Output is correct
22 Correct 1343 ms 224092 KB Output is correct
23 Correct 1290 ms 205144 KB Output is correct
24 Correct 726 ms 171100 KB Output is correct
25 Correct 1056 ms 164064 KB Output is correct
26 Correct 1602 ms 169264 KB Output is correct
27 Correct 1795 ms 170528 KB Output is correct
28 Correct 1949 ms 174596 KB Output is correct
29 Correct 1568 ms 172936 KB Output is correct
30 Correct 1027 ms 160464 KB Output is correct
31 Correct 1952 ms 144672 KB Output is correct
32 Correct 1958 ms 144604 KB Output is correct
33 Correct 2105 ms 144828 KB Output is correct
34 Correct 1972 ms 144584 KB Output is correct
35 Correct 1926 ms 144344 KB Output is correct
36 Correct 1891 ms 144496 KB Output is correct
37 Correct 1125 ms 176012 KB Output is correct
38 Correct 3302 ms 300740 KB Output is correct
39 Execution timed out 5101 ms 501464 KB Time limit exceeded
40 Halted 0 ms 0 KB -