Submission #738280

#	Time	Username	Problem	Language	Result	Execution time	Memory
738280		mosiashvililuka	I want to be the very best too! (NOI17_pokemonmaster)	C++14	71 / 100	4187 ms	21920 KiB

pokemonmaster

#include<bits/stdc++.h>
using namespace std;
const int T=317;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,tp,pas,Ffx[50009],sub1,f[50009],fen[50009],TP[100009],msh[100009],zm[100009],ones[100009],QI,bo[100009],I,ZI,ans[100009],ZOMA[100009],KK[100009];
//pair <pair <int, int>, int> p[100009];
pair <int, int> Q[100009],Z[100009];
int X[100009],Y[100009],col[100009];
vector <vector <int> > L,P,Lbo,id,DZ;
vector <int> v[100009],V[100009];
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 fnd(int q){
    if(msh[q]==q) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
    q=fnd(q);w=fnd(w);
    if(q==w) return;
    msh[w]=q;
    if(zm[q]==zm[w]) zm[q]++;
    ones[q]+=ones[w];
    ZOMA[q]+=ZOMA[w];
}
void ADD(int q){
    //cout<<"ADD "<<q<<"\n";
    bo[q]=1;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(bo[(*it)]==0) continue;
        //cout<<"mrg "<<q<<" "<<(*it)<<"\n";
        mrg(q,(*it));
    }
}
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;id=L;
    for(i=1; i<=a; i++){
        for(j=1; j<=b; j++){
            cin>>L[i][j];
            id[i][j]=(i-1)*b+j;
        }
    }
    DZ=L;
    for(i=1; i<=a; i++){
        for(j=1; j<=b; j++){
            for(ii=-1; ii<=1; ii++){
                for(jj=-1; jj<=1; jj++){
                    if(ii!=0&&jj!=0) continue;
                    if(ii==0&&jj==0) continue;
                    c=i+ii;d=j+jj;
                    //cout<<c<<" "<<d<<" cd\n";
                    if(c<1||c>a||d<1||d>b) continue;
                    //cout<<"Fdsf\n";
                    v[id[i][j]].push_back(id[c][d]);
                }
            }
        }
    }
    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;
    }




    int L,R;

    for(t=1; t<=tes; t++){
        cin>>TP[t];
        //cin>>p[t].first.first>>p[t].first.second>>p[t].second;
        cin>>X[t]>>Y[t]>>col[t];
        swap(X[t],Y[t]);
    }
    //
    for(ii=1; ; ii++){
        if((ii-1)*T+1>tes) break;
        L=(ii-1)*T+1;
        R=min(tes,ii*T);
        if(ii!=1){
            for(i=L-T; i<L; i++){
                if(TP[i]==1){
                    P[X[i]][Y[i]]=col[i];
                }
            }
        }
        QI=0;
        for(i=1; i<=a; i++){
            for(j=1; j<=b; j++){
                msh[id[i][j]]=id[i][j];zm[id[i][j]]=0;ZOMA[id[i][j]]=1;
                if(P[i][j]==1) ones[id[i][j]]=1; else ones[id[i][j]]=0;
                QI++;Q[QI]={DZ[i][j],id[i][j]};
                bo[id[i][j]]=0;
            }
        }
        //cout<<ones[id[1][1]]<<" "<<ones[id[1][2]]<<" "<<ones[id[1][3]]<<" ones\n";
        sort(Q+1,Q+QI+1);
        ZI=0;
        for(t=L; t<=R; t++){
            if(TP[t]==2){
                ZI++;Z[ZI]={col[t],t};
            }
        }
        sort(Z+1,Z+ZI+1);
        //
        //
        /*for(ii=1; ii<=QI; ii++){
            ADD(Q[ii].second);
        }*/
        /*cout<<QI<<" QI"<<endl;
        for(i=1; i<=QI; i++){
            cout<<Q[i].first<<" "<<Q[i].second<<endl;
        }
        cout<<ZI<<" ZI"<<endl;
        for(i=1; i<=ZI; i++){
            cout<<Z[i].first<<" "<<Z[i].second<<endl;
        }*/
        //return 0;
        I=1;
        for(int ii=1; ii<=ZI; ii++){
            //cout<<ii<<endl;
            //if(ii==2) return 0;
            t=Z[ii].second;
            while(I<=QI&&Q[I].first<=col[t]){
                ADD(Q[I].second);I++;
            }
            //if(ii==2) return 0;
            if(DZ[X[t]][Y[t]]>col[t]){
                ans[t]=0;
                continue;
            }
            c=fnd(id[X[t]][Y[t]]);
            zx=ones[c];xc=ZOMA[c]-ones[c];
            //cout<<zx<<" "<<xc<<"\n";
            for(i=L; i<t; i++){
                KK[id[X[i]][Y[i]]]=P[X[i]][Y[i]];
            }
            //cout<<ii<<"   "<<I<<" iiI\n";
            //if(t==tes) cout<<zx<<" "<<xc<<" tt\n";
            for(i=L; i<t; i++){
                if(TP[i]!=1) continue;
                if(fnd(id[X[i]][Y[i]])!=c) continue;
                //cout<<"iquery "<<i<<"\n";
                if(P[X[i]][Y[i]]==1) zx--; else xc--;
                P[X[i]][Y[i]]=col[i];
                if(P[X[i]][Y[i]]==1) zx++; else xc++;
            }
            for(i=L; i<t; i++){
                P[X[i]][Y[i]]=KK[id[X[i]][Y[i]]];
            }
            pas=0;
            if(zx!=0) pas++;
            if(xc!=0) pas++;
            ans[t]=pas;
            //if(ii==2) return 0;
        }
        //return 0;
    }
    for(t=1; t<=tes; t++){
        if(TP[t]==1) continue;
        cout<<ans[t]<<"\n";
    }
    return 0;
}

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