Submission #1190397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190397		user736482	Road Service 2 (JOI24_ho_t5)	C++20	48 / 100	1106 ms	404540 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][24],bst2[1000007][24],bst3[1000007][24];
bool odw[1000007];
ll naj[1000007][2];
pair<ll,ll>spoj[1000007];
void dfs(ll v,ll czyj){
    if(odw[v])return;
    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<ll,ll>skok(pair<ll,ll>ak,ll ile){
    return {max(bst2[ak.ss][ile],bst[ak.ff][ile]),max(bst[ak.ss][ile],bst3[ak.ff][ile])};
}
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]});
    }
    if(s.size()==1){
        cout<<0<<"\n";
        return;
    }
    for(auto it=s.begin();it!=s.end();it++){
        v2.pb((*it).ff);
    }
    for(ll i=v2.size()-1;i>=0;i--){
        if(v.size() && v.back().ss<=v2[i].ss)continue;
        v.pb(v2[i]);
    }
    sort(v.begin(),v.end());
    ll ile=23;
    unordered_map<ll,pair<ll,ll>>mp;
    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++){
        pair<ll,ll>pr={mp[i].ss,mp[i+1].ss};
        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;
        }
        while(skok(pr,ile).ss>=v[mp[i].ff+1].ff){
            ile--;
            if(ile<0){
                ile=23;
                break;
            }
        }
        if(ile!=23){
            pr=skok(pr,ile);
            mp[i+(1<<ile)]={mp[i].ff,pr.ff};
            mp[i+1+(1<<ile)]={mp[i].ff,pr.ss};
            i=i-1+(1<<ile);
            continue;
        }
        
        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'){
                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'){
                g[i*m+j].pb(i*m+j-m);
                g[i*m+j-m].pb(i*m+j);
            }
        }
    }
    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);
            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;
            prz.pb({spoj[i]});
        }
    }
    sort(prz.begin(),prz.end());
    reverse(prz.begin(),prz.end());
    ll akkon=-1;
    for(ll i=0;i<n;i++){
        najdalej[i]=i;
        bst2[i][0]=i;
        bst[i][0]=i;
        bst3[i][0]=i;
        if(i){
        bst[i][0]=max(bst[i][0],bst[i-1][0]);
        bst3[i][0]=max(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++){
                
                bst3[i][0]=j;
                najdalej[i]=j;
            }
            if(kszt[i]==1)
                bst[i][0]=bst3[i][0];
            akkon=max(akkon,prz.back().ss);
            prz.pop_back();
        }
    }
    for(ll i=0;i<n;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<24;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 i=0;i<q;i++)solve();
}

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