Submission #1190312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190312		user736482	Road Service 2 (JOI24_ho_t5)	C++20	43 / 100	3109 ms	431572 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

ll n,q,s,t,a,b,c,ans,k,e,m,h,w,u;
vector<ll>g[1000007];
vector<pair<ll,ll>>prz;
char ch;
ll moj[1000007],kszt[1000007],pop1[1000007],najdalej[1000007];
ll bst[1000007][22],bst2[1000007][22],bst3[1000007][22];//z[i] placac2^[j] lub 2^[j] -1 lub 2^[j] +1
bool odw[1000007];
ll naj[1000007][2];
pair<ll,ll>spoj[1000007];

void dfs(ll v,ll czyj){
    
    if(odw[v])return;
    //cout<<v<<" ";
    moj[v]=czyj;
    odw[v]=1;
    spoj[czyj].ff=min(spoj[czyj].ff,v/m);
    spoj[czyj].ss=max(spoj[czyj].ss,v/m);
    for(ll i : g[v])dfs(i,czyj);
}

/*pair<pair<ll,ll>,ll>pier(ll strt,ll pocz){//<koszt i koniec>,drugi koniec  - najtanszy koniec >=pocz i najalszy w kosztcie min+1
    ll akzap=0;
    ll p1=strt;
    ll p2=strt;
    if(strt==pocz){
        return {{0,strt},strt};
    }
    ll akpot=21;
    ll kszt=1;
    //cout<<pocz<<" "<<p1<<" "<<p2<<" "<<kszt<<" "<<akpot<<"\n";
    while(p2<pocz){
        while(max(bst2[p2][akpot],bst[p1][akpot])>=pocz)akpot--;
        if(akpot<0)break;
        ll np1=max(bst2[p2][akpot],bst[p1][akpot]);
        ll np2=max(bst3[p2][akpot],bst2[p1][akpot]);
        kszt+=(1<<akpot);
        if(kszt>=(1<<22))
            return {{-1,-1},-1};
        p1=np1;
        p2=np2;//cout<<p1<<" "<<p2<<" "<<kszt<<" "<<akpot<<"\n";
        
    }//return {{0,0},0};
    ll np1=max(bst2[p2][0],bst[p1][0]);
    ll np2=max(bst3[p2][0],bst2[p1][0]);
    p1=np1;
    p2=np2;
    //cout<<kszt<<" "<<p1<<" "<<p2;
    //cout<<"\n\n";
    return {{kszt,p1},p2};
}*/

void solve(){
    cin>>a;
    set<pair<pair<ll,ll>,ll>>s;
    vector<pair<ll,ll>>v,v2;
    for(ll i=0;i<a;i++){
        cin>>b>>c;
        b--;
        c--;
        b=b*m+c;
        s.insert({spoj[moj[b]],moj[b]});
        //cout<<spoj[moj[b]].ff<<" "<<spoj[moj[b]].ss<<"\n";
    }//cout<<"\n";
    //return;
    if(s.size()==1){
        cout<<0<<"\n";
        return;
    }
    for(auto it=s.begin();it!=s.end();it++){
        //if(v.size() && (*it).ff.ss<=v.back().ss)continue;
        v2.pb((*it).ff);
        //cout<<v.back().ff<<" "<<v.back().ss<<"\n";
    } //cout<<"\n";
    for(ll i=v2.size()-1;i>=0;i--){
        if(v.size() && v.back().ss<=v2[i].ss)continue;
        v.pb(v2[i]);
        //cout<<v.back().ff<<" "<<v.back().ss<<"\n";
    }
    sort(v.begin(),v.end());
    //cout<<"\n\n";
    unordered_map<ll,pair<ll,ll>>mp;//koszt, <ostatni wziety,zasieg>
    mp[2]={lower_bound(v.begin(),v.end(),(pair<ll,ll>){v[0].ss+1,-INFL})-v.begin()-1,najdalej[v[0].ss]};
    if(pop1[v[0].ss]>=v[0].ff)
    mp[1]={lower_bound(v.begin(),v.end(),(pair<ll,ll>){pop1[v[0].ss]+1,-INFL})-v.begin()-1,najdalej[pop1[v[0].ss]]};
    for(ll i=1+(pop1[v[0].ss]<v[0].ff);1;i++){
        //cout<<i<<" "<<mp[i].ff<<" "<<mp[i].ss<<"\n";
        if(mp[i].ff==v.size()-1){
            cout<<i<<"\n";
            return;
        }
        if(bst3[mp[i].ss][0]==mp[i].ss && v[mp[i].ff+1].ff>mp[i].ss){
            
            cout<<-1<<"\n";
            return;
        }
        ll kon=min(mp[i].ss,v[mp[i].ff+1].ss);
        mp[i+2]=max(mp[i],max(mp[i+2],{lower_bound(v.begin(),v.end(),(pair<ll,ll>){kon+1,-INFL})-v.begin()-1,najdalej[kon]}));
        mp[i+1]=max(mp[i],max(mp[i+1],{lower_bound(v.begin(),v.end(),(pair<ll,ll>){pop1[kon]+1,-INFL})-v.begin()-1,najdalej[pop1[kon]]}));
    }
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    for(ll i=0;i<n;i++){
        for(ll j=1;j<m;j++){
            cin>>ch;
            if(ch=='1'){
            //    cout<<i*m+j<<" "<<i*m+j-1<<"\n";
                g[i*m+j].pb(i*m+j-1);
                g[i*m+j-1].pb(i*m+j);
            }
        }
    }
    for(ll i=1;i<n;i++){
        for(ll j=0;j<m;j++){
            cin>>ch;
            if(ch=='1'){
           //     cout<<i*m+j<<" "<<i*m+j-m<<"\n";
                g[i*m+j].pb(i*m+j-m);
                g[i*m+j-m].pb(i*m+j);
            }
        }
    }//cout<<"\n\n";
    for(ll i=0;i<n;i++)cin>>kszt[i];
    for(ll i=0;i<m*n;i++){
        if(!odw[i]){
            spoj[i]={INF,0};
            dfs(i,i);
            //cout<<spoj[i].ff<<" "<<spoj[i].ss<<"\n";
            naj[i][0]=-1;
            for(ll j=spoj[i].ff;j<=spoj[i].ss;j++){
                if(kszt[i]==1)
                    naj[i][0]=j;
            }
            naj[i][1]=spoj[i].ss;
            //cout<<naj[i][0]<<"\n";
            prz.pb({spoj[i]});
        }
    }
    //cout<<"\n";
    sort(prz.begin(),prz.end());
    reverse(prz.begin(),prz.end());
    ll akkon=-1;//cout<<"\n";
    for(ll i=0;i<n;i++){
        najdalej[i]=i;
        if(i){
        bst[i][0]=bst[i-1][0];
        bst3[i][0]=bst3[i-1][0];
        najdalej[i]=max(najdalej[i],najdalej[i-1]);
        }
        while(prz.back().ff==i){
            for(ll j=akkon+1;j<=prz.back().ss;j++){
                if(kszt[j]==1)
                    bst[i][0]=j;
                bst3[i][0]=j;
                najdalej[i]=j;
            }
            akkon=max(akkon,prz.back().ss);
            bst2[i][0]=i;   
            prz.pop_back();
        }
    }//cout<<"\n";
    for(ll i=0;i<n;i++){
        //cout<<najdalej[i]<<" ";
        pop1[i]=-1;
        if(i)pop1[i]=pop1[i-1];
        if(kszt[i]==1)pop1[i]=i;
        bst3[i][0]=max(bst3[i][0],bst[bst[i][0]][0]);
    }
    for(ll j=1;j<22;j++){
        for(ll i=0;i<n;i++){
            bst[i][j]=min(bst[bst[i][j-1]][j-1],bst2[bst3[i][j-1]][j-1]);
            bst2[i][j]=min(bst[bst2[i][j-1]][j-1],bst2[bst[i][j-1]][j-1]);
            bst3[i][j]=min(bst[bst3[i][j-1]][j-1],bst3[bst[i][j-1]][j-1]);
        }
    }
    for(ll j=0;j<3;j++){
            for(ll i=0;i<n;i++){
        
            //cout<<bst[i][j]<<" "<<bst2[i][j]<<" "<<bst3[i][j]<<"\n";
        }
    }
    for(ll i=0;i<q;i++)solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 0 / 11
• Subtask 5: 0 / 6
• Subtask 6: 12 / 12
• Subtask 7: 0 / 26
• Subtask 8: 0 / 14