oj.uz

Submission #738280

# Submission time Handle Problem Language Result Execution time Memory
738280 2023-05-08T11:39:11 Z mosiashvililuka I want to be the very best too! (NOI17_pokemonmaster) C++14
71 / 100
 4187 ms 21920 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14416 KB Output is correct
2 Correct 27 ms 14728 KB Output is correct
3 Correct 26 ms 14728 KB Output is correct
4 Correct 28 ms 14472 KB Output is correct
5 Correct 27 ms 14668 KB Output is correct
6 Correct 36 ms 14712 KB Output is correct
7 Correct 31 ms 14412 KB Output is correct
8 Correct 38 ms 14708 KB Output is correct
9 Correct 25 ms 14452 KB Output is correct
10 Correct 27 ms 14752 KB Output is correct
11 Correct 29 ms 14704 KB Output is correct
12 Correct 26 ms 14720 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13812 KB Output is correct
2 Correct 22 ms 13652 KB Output is correct
3 Correct 24 ms 13688 KB Output is correct
4 Correct 31 ms 16920 KB Output is correct
5 Correct 35 ms 17712 KB Output is correct
6 Correct 38 ms 17612 KB Output is correct
7 Correct 24 ms 11364 KB Output is correct
8 Correct 27 ms 11384 KB Output is correct
9 Correct 26 ms 11172 KB Output is correct
10 Correct 26 ms 11580 KB Output is correct
11 Correct 25 ms 11300 KB Output is correct
12 Correct 25 ms 11284 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1670 ms 17472 KB Output is correct
2 Correct 1648 ms 17752 KB Output is correct
3 Correct 1471 ms 17544 KB Output is correct
4 Correct 1637 ms 21524 KB Output is correct
5 Correct 1820 ms 21920 KB Output is correct
6 Correct 1897 ms 21888 KB Output is correct
7 Correct 4168 ms 15532 KB Output is correct
8 Correct 4001 ms 15780 KB Output is correct
9 Correct 4171 ms 15784 KB Output is correct
10 Correct 4069 ms 15636 KB Output is correct
11 Correct 4187 ms 15972 KB Output is correct
12 Correct 4122 ms 16000 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14416 KB Output is correct
2 Correct 27 ms 14728 KB Output is correct
3 Correct 26 ms 14728 KB Output is correct
4 Correct 28 ms 14472 KB Output is correct
5 Correct 27 ms 14668 KB Output is correct
6 Correct 36 ms 14712 KB Output is correct
7 Correct 31 ms 14412 KB Output is correct
8 Correct 38 ms 14708 KB Output is correct
9 Correct 25 ms 14452 KB Output is correct
10 Correct 27 ms 14752 KB Output is correct
11 Correct 29 ms 14704 KB Output is correct
12 Correct 26 ms 14720 KB Output is correct
13 Correct 61 ms 14620 KB Output is correct
14 Correct 93 ms 14960 KB Output is correct
15 Correct 106 ms 14976 KB Output is correct
16 Correct 91 ms 14536 KB Output is correct
17 Correct 80 ms 14892 KB Output is correct
18 Correct 64 ms 15224 KB Output is correct
19 Correct 76 ms 14444 KB Output is correct
20 Correct 93 ms 14836 KB Output is correct
21 Correct 91 ms 14504 KB Output is correct
22 Correct 92 ms 14956 KB Output is correct
23 Correct 85 ms 14940 KB Output is correct
24 Correct 86 ms 15056 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14416 KB Output is correct
2 Correct 27 ms 14728 KB Output is correct
3 Correct 26 ms 14728 KB Output is correct
4 Correct 28 ms 14472 KB Output is correct
5 Correct 27 ms 14668 KB Output is correct
6 Correct 36 ms 14712 KB Output is correct
7 Correct 31 ms 14412 KB Output is correct
8 Correct 38 ms 14708 KB Output is correct
9 Correct 25 ms 14452 KB Output is correct
10 Correct 27 ms 14752 KB Output is correct
11 Correct 29 ms 14704 KB Output is correct
12 Correct 26 ms 14720 KB Output is correct
13 Correct 22 ms 13812 KB Output is correct
14 Correct 22 ms 13652 KB Output is correct
15 Correct 24 ms 13688 KB Output is correct
16 Correct 31 ms 16920 KB Output is correct
17 Correct 35 ms 17712 KB Output is correct
18 Correct 38 ms 17612 KB Output is correct
19 Correct 24 ms 11364 KB Output is correct
20 Correct 27 ms 11384 KB Output is correct
21 Correct 26 ms 11172 KB Output is correct
22 Correct 26 ms 11580 KB Output is correct
23 Correct 25 ms 11300 KB Output is correct
24 Correct 25 ms 11284 KB Output is correct
25 Correct 1670 ms 17472 KB Output is correct
26 Correct 1648 ms 17752 KB Output is correct
27 Correct 1471 ms 17544 KB Output is correct
28 Correct 1637 ms 21524 KB Output is correct
29 Correct 1820 ms 21920 KB Output is correct
30 Correct 1897 ms 21888 KB Output is correct
31 Correct 4168 ms 15532 KB Output is correct
32 Correct 4001 ms 15780 KB Output is correct
33 Correct 4171 ms 15784 KB Output is correct
34 Correct 4069 ms 15636 KB Output is correct
35 Correct 4187 ms 15972 KB Output is correct
36 Correct 4122 ms 16000 KB Output is correct
37 Correct 61 ms 14620 KB Output is correct
38 Correct 93 ms 14960 KB Output is correct
39 Correct 106 ms 14976 KB Output is correct
40 Correct 91 ms 14536 KB Output is correct
41 Correct 80 ms 14892 KB Output is correct
42 Correct 64 ms 15224 KB Output is correct
43 Correct 76 ms 14444 KB Output is correct
44 Correct 93 ms 14836 KB Output is correct
45 Correct 91 ms 14504 KB Output is correct
46 Correct 92 ms 14956 KB Output is correct
47 Correct 85 ms 14940 KB Output is correct
48 Correct 86 ms 15056 KB Output is correct
49 Incorrect 1620 ms 18512 KB Output isn't correct
50 Halted 0 ms 0 KB -