Submission #1181218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181218		user736482	Road Service 2 (JOI24_ho_t5)	C++20	0 / 100	659 ms	359664 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 100000000099

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];
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 {{INFL,-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<pair<ll,ll>,ll>>v;
    //cout<<"                  ";
    for(ll i=0;i<a;i++){
        cin>>b>>c;
        b--;
        c--;
        b=b*m+c;
        //cout<<b<<" "<<moj[b]<<" "<<spoj[moj[b]].ff<<" "<<spoj[moj[b]].ss<<"   ";
        s.insert({spoj[moj[b]],moj[b]});
    }//cout<<"\n";
    if(s.size()==1){
        cout<<""<<0<<"\n";
        return;
    }
    for(auto it=s.begin();it!=s.end();it++){
        //cout<<(*it).ff.ff<<" "<<(*it).ff.ss<<"\n";
        if(v.size() && ((*it).ff.ss<=v.back().ff.ss || (*it).ff.ff==v.back().ff.ff))continue;
        v.pb(*it);
    }
    pair<ll,ll>bst={1,naj[v[0].ss][0]},bst2={2,naj[v[0].ss][1]};
    //cout<<bst.ss<<" "<<bst2.ss<<" "<<v.size()<<"\n\n";
    //return;
    for(ll i=1;i<v.size();i++){
        pair<pair<ll,ll>,ll>p1=pier(bst.ss,v[i].ff.ff),p2=pier(bst2.ss,v[i].ff.ff);
        if(p2.ff.ff==-1){
          //  cout<<""<<-1<<"\n";
          //  return;
        }
        //return;
        //cout<<p2.ff.ff<<" "<<p1.ff.ff<<"\n";
        p1.ff.ff+=bst.ff;
        p2.ff.ff+=bst2.ff;
        if(p1.ff.ss>v[i].ff.ss){
            p1.ff.ff=p1.ff.ff+1-kszt[p1.ff.ss];
            p1.ff.ss=naj[v[i].ss][0];
            p1.ss=naj[v[i].ss][1];
            //cout<<"xd";
        }
        else if(p1.ss>v[i].ff.ss){
            p1.ss=naj[v[i].ss][1];
            //cout<<"zd";
        }
        if(p2.ff.ss>v[i].ff.ss){
            p2.ff.ff=p2.ff.ff+1-kszt[p2.ff.ss];
            p2.ff.ss=naj[v[i].ss][0];
            p2.ss=naj[v[i].ss][1];
        }
        else if(p2.ss>v[i].ff.ss){
            p2.ss=naj[v[i].ss][1];
        }
        if(p1.ff.ff<p2.ff.ff){
            bst={p1.ff.ff,p1.ff.ss};
            bst2={p1.ff.ff+1,p1.ss};
            if(p2.ff.ff+1==p1.ff.ff)
                bst2.ss=max(bst2.ss,p2.ff.ss);
        }
        else if(p1.ff.ff>p2.ff.ff){
            bst={p2.ff.ff,p2.ff.ss};
            bst2={p2.ff.ff+1,p2.ss};
            if(p1.ff.ff+1==p2.ff.ff)
                bst2.ss=max(bst2.ss,p1.ff.ss);
        }
        else{
            bst={p2.ff.ff,p2.ff.ss};
            bst2={p2.ff.ff+1,p2.ss};
            bst.ss=max(bst.ss,p1.ff.ss);
            bst2.ss=max(bst2.ss,p1.ss);
        }
    }
    if(bst.ff>=INFL)bst.ff=-1;
    cout<<""<<bst.ff<<"\n";
}

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<<" ";
            naj[i][0]=-1;
            for(ll j=spoj[i].ff;j<=spoj[i].ss;j++){
                if(kszt[j]==1)
                    naj[i][0]=j;
            }
            naj[i][1]=spoj[i].ss;
            //cout<<"\n";
            //cout<<naj[i][0]<<"\n";
            prz.pb({spoj[i]});
        }
    }
    
    sort(prz.begin(),prz.end());
    reverse(prz.begin(),prz.end());
    ll akkon=-1;
    for(ll i=0;i<n;i++){
        if(i){
        bst[i][0]=bst[i-1][0];
        bst3[i][0]=bst3[i-1][0];
        }
        bst[i][0]=max(i,bst[i][0]);
            bst3[i][0]=max(i,bst3[i][0]);
        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;
            }
            akkon=prz.back().ss;
            
            prz.pop_back();
        }
        bst2[i][0]=i;   
    }
    for(ll i=0;i<n;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]=max(bst[bst[i][j-1]][j-1],bst2[bst3[i][j-1]][j-1]);
            bst2[i][j]=max(bst[bst2[i][j-1]][j-1],bst2[bst[i][j-1]][j-1]);
            bst3[i][j]=max(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";
        }
        //cout<<"\n";
    }
    //return 0;
    for(ll i=0;i<q;i++)solve();
}

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