oj.uz

Submission #738257

# Submission time Handle Problem Language Result Execution time Memory
738257 2023-05-08T10:27:39 Z mosiashvililuka I want to be the very best too! (NOI17_pokemonmaster) C++14
51 / 100
 92 ms 9916 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,tp,pas,Ffx[50009],sub1,f[50009],fen[50009];
vector <vector <int> > L,P,Lbo;
set <int> s[50009];
void dfs(int q, int w){
    if(q<1||q>a||w<1||w>b) return;
    if(L[q][w]>e) return;
    if(Lbo[q][w]==t) return;
    Lbo[q][w]=t;
    if(Ffx[P[q][w]]!=t){
        pas++;
        Ffx[P[q][w]]=t;
    }
    dfs(q-1,w);
    dfs(q+1,w);
    dfs(q,w-1);
    dfs(q,w+1);
}
void upd(int q, int w){
    while(q<=a+3){
        fen[q]+=w;
        q=q+(q&(-q));
    }
}
int read(int q){
    int sm=0;
    while(q>0){
        sm+=fen[q];
        q=q-(q&(-q));
    }
    return sm;
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b>>tes;
    L.resize(a+2);P.resize(a+2);
    for(i=0; i<a+2; i++){
        L[i].resize(b+2);P[i].resize(b+2);
    }
    Lbo=L;
    for(i=1; i<=a; i++){
        for(j=1; j<=b; j++){
            cin>>L[i][j];
        }
    }
    for(i=1; i<=a; i++){
        for(j=1; j<=b; j++){
            cin>>P[i][j];
        }
    }


    if(a!=1) sub1=1;
    for(j=1; j<=b; j++){
        if(L[1][j]!=j) sub1=1;
    }

    if(sub1==0){
        //cout<<"sub1\n";
        set <int>::iterator it,tt;
        a=b;
        for(i=1; i<=a; i++) f[i]=P[1][i];
        //
        for(i=1; i<=a; i++){
            s[f[i]].insert(i);
        }
        for(i=1; i<=a; i++){
            if(Ffx[f[i]]!=0) continue;
            Ffx[f[i]]=1;
            it=s[f[i]].begin();
            upd((*it),1);
        }
        for(t=1; t<=tes; t++){
            cin>>tp;
            if(tp==1){
                cin>>c>>d>>e;swap(c,d);

                c=d;
                it=s[f[c]].begin();
                upd((*it),-1);
                s[f[c]].erase(s[f[c]].lower_bound(c));
                if(s[f[c]].size()>0){
                    it=s[f[c]].begin();
                    upd((*it),1);
                }
                //
                f[c]=e;
                //
                if(s[f[c]].size()>0){
                    it=s[f[c]].begin();
                    upd((*it),-1);
                }
                s[f[c]].insert(c);
                it=s[f[c]].begin();
                upd((*it),1);
                continue;
            }
            if(tp==2){
                cin>>c>>d>>e;swap(c,d);

                c=d;
                if(c>e){
                    cout<<"0\n";
                    continue;
                }
                cout<<read(min(a,e))<<"\n";
            }
        }
        return 0;
    }



    if(tes<=10){
        for(t=1; t<=tes; t++){
            cin>>tp;
            if(tp==1){
                cin>>c>>d>>e;swap(c,d);
                P[c][d]=e;
                continue;
            }
            if(tp==2){
                cin>>c>>d>>e;pas=0;swap(c,d);
                dfs(c,d);
                cout<<pas<<"\n";
                continue;
            }
        }
        return 0;
    }

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6996 KB Output is correct
2 Correct 22 ms 7884 KB Output is correct
3 Correct 19 ms 7856 KB Output is correct
4 Correct 18 ms 7628 KB Output is correct
5 Correct 20 ms 7816 KB Output is correct
6 Correct 17 ms 7892 KB Output is correct
7 Correct 19 ms 7552 KB Output is correct
8 Correct 20 ms 7784 KB Output is correct
9 Correct 16 ms 7516 KB Output is correct
10 Correct 21 ms 7848 KB Output is correct
11 Correct 21 ms 7876 KB Output is correct
12 Correct 20 ms 7896 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6356 KB Output is correct
2 Correct 18 ms 6120 KB Output is correct
3 Correct 12 ms 6248 KB Output is correct
4 Correct 16 ms 8064 KB Output is correct
5 Correct 18 ms 8736 KB Output is correct
6 Correct 21 ms 8788 KB Output is correct
7 Correct 15 ms 4692 KB Output is correct
8 Correct 12 ms 4692 KB Output is correct
9 Correct 13 ms 4424 KB Output is correct
10 Correct 18 ms 4804 KB Output is correct
11 Correct 15 ms 4604 KB Output is correct
12 Correct 16 ms 4564 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6996 KB Output is correct
2 Correct 22 ms 7884 KB Output is correct
3 Correct 19 ms 7856 KB Output is correct
4 Correct 18 ms 7628 KB Output is correct
5 Correct 20 ms 7816 KB Output is correct
6 Correct 17 ms 7892 KB Output is correct
7 Correct 19 ms 7552 KB Output is correct
8 Correct 20 ms 7784 KB Output is correct
9 Correct 16 ms 7516 KB Output is correct
10 Correct 21 ms 7848 KB Output is correct
11 Correct 21 ms 7876 KB Output is correct
12 Correct 20 ms 7896 KB Output is correct
13 Correct 53 ms 9220 KB Output is correct
14 Correct 76 ms 9548 KB Output is correct
15 Correct 78 ms 9428 KB Output is correct
16 Correct 92 ms 9112 KB Output is correct
17 Correct 89 ms 9488 KB Output is correct
18 Correct 54 ms 9916 KB Output is correct
19 Correct 69 ms 9148 KB Output is correct
20 Correct 76 ms 9420 KB Output is correct
21 Correct 78 ms 9260 KB Output is correct
22 Correct 77 ms 9672 KB Output is correct
23 Correct 71 ms 9648 KB Output is correct
24 Correct 63 ms 9676 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6996 KB Output is correct
2 Correct 22 ms 7884 KB Output is correct
3 Correct 19 ms 7856 KB Output is correct
4 Correct 18 ms 7628 KB Output is correct
5 Correct 20 ms 7816 KB Output is correct
6 Correct 17 ms 7892 KB Output is correct
7 Correct 19 ms 7552 KB Output is correct
8 Correct 20 ms 7784 KB Output is correct
9 Correct 16 ms 7516 KB Output is correct
10 Correct 21 ms 7848 KB Output is correct
11 Correct 21 ms 7876 KB Output is correct
12 Correct 20 ms 7896 KB Output is correct
13 Correct 14 ms 6356 KB Output is correct
14 Correct 18 ms 6120 KB Output is correct
15 Correct 12 ms 6248 KB Output is correct
16 Correct 16 ms 8064 KB Output is correct
17 Correct 18 ms 8736 KB Output is correct
18 Correct 21 ms 8788 KB Output is correct
19 Correct 15 ms 4692 KB Output is correct
20 Correct 12 ms 4692 KB Output is correct
21 Correct 13 ms 4424 KB Output is correct
22 Correct 18 ms 4804 KB Output is correct
23 Correct 15 ms 4604 KB Output is correct
24 Correct 16 ms 4564 KB Output is correct
25 Incorrect 9 ms 4460 KB Output isn't correct
26 Halted 0 ms 0 KB -