Submission #738257

#	Time	Username	Problem	Language	Result	Execution time	Memory
738257		mosiashvililuka	I want to be the very best too! (NOI17_pokemonmaster)	C++14	51 / 100	92 ms	9916 KiB

pokemonmaster

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