제출 #1330618

#제출 시각아이디문제언어결과실행 시간메모리
1330618user736482Escape Route 2 (JOI24_escape2)C++20
54 / 100
3093 ms48856 KiB
#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 INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
ll n,t,q,a,b,c;
vii mj[100007];
vector<vii>sc[100007];
vi nx[100007];
vii zap[100007];
ll ns[300007];
vi ksz[100007];
vi sz[100007];
void solve(){
    cin>>n>>t;
    n--;
    for(ll i=1;i<=n;i++){
        cin>>a;
        while(a--){
            cin>>b>>c;mj[i].pb({c,b});
        }
        sort(al(mj[i]));
        vii pm;
        for(pii j : mj[i]){
            if(pm.empty() || pm.back().ff<j.ss)pm.pb({j.ss,j.ff});

        }
        swap(mj[i],pm);
    }
    for(ll i=1;i<n;i++){
        for(ll j=0;j<mj[i].size();j++){
            if(mj[i+1].back().ff<mj[i][j].ss)nx[i].pb(0);
            else nx[i].pb(lower_bound(al(mj[i+1]),pii{mj[i][j].ss,-2137})-mj[i+1].begin());
            ksz[i].pb((mj[i+1][nx[i][j]].ss-mj[i][j].ss+t*(mj[i+1][nx[i][j]].ff<mj[i][j].ss)));
            //cout<<ksz[i].back()<< " ";
        }
        //cout<<"\n";
    }
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<mj[i].size();j++){
            sz[i].pb(mj[i][j].ss-mj[i][j].ff);
        }
    }
    cin>>q;
    for(ll i=0;i<q;i++){ns[i]=INFL;
        cin>>a>>b;zap[b-1].pb({a,i});
    }
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<mj[i].size();j++){
            sc[i].pb({{j,0}});
        }
        for(ll j=0;j<mj[i-1].size();j++){
            ll ns=nx[i-1][j];
            sc[i-1][j].pb({ns,sc[i-1][j].back().ss+ksz[i-1][j]});
            if(sc[i-1][j].size()>sc[i][ns].size())swap(sc[i-1][j],sc[i][ns]);
            ll df=sc[i][ns].back().ss-sc[i-1][j].back().ss;
            ll dfs=sc[i][ns].size()-sc[i-1][j].size();
            for(ll k=0;k<sc[i-1][j].size();k++){
                //cout<<j<<" "<<k<<" "<<dfs<<" "<<flush<<sz[k-sc[i-1][j].size()+i+1][sc[i][ns][k+dfs].ff]<<" "<<flush<<sc[i-1][j][k].ff-sz[k-sc[i-1][j].size()+i+1][sc[i-1][j][k].ff]+df<<"   "<<flush;
                if(sc[i][ns][k+dfs].ss-sz[k-sc[i-1][j].size()+i+1][sc[i][ns][k+dfs].ff]<sc[i-1][j][k].ss-sz[k-sc[i-1][j].size()+i+1][sc[i-1][j][k].ff]+df)
                sc[i][ns][k+dfs]=sc[i-1][j][k]+pii{0,df};
            }
        }
        // for(ll k=0;k<mj[i].size();k++){
        //     cout<<sc[i][k]<<"\n";
        // }
        // cout<<endl;
        for(pii j: zap[i]){
            for(ll k=0;k<mj[i].size();k++){
                ll id=sc[i][k].size()-1-i+j.ff;
                if(id<0)continue;
                ll kt=sc[i][k][id].ff;
               // cout<<id<<" "<<kt<<" "<<j.ff<<endl;
                ns[j.ss]=min(ns[j.ss],sc[i][k].back().ss-sc[i][k][id].ss+sz[j.ff][kt]);
                //cout<<"xd"<<flush;
            }
        }
       // cout<<"xd"<<flush;
    }
    for(ll i=0;i<q;i++)cout<<ns[i]<<"\n";
}
int main(){
    fct[0]=1;
    for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...