Submission #1245323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245323		Hanksburger	Escape Route 2 (JOI24_escape2)	C++17	14 / 100	3116 ms	909480 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int sz1=405, sz2=255;
vector<pair<int, ll> > nxt[100005], nn[100005], pp[100005], edge[sz2][100005], vec[100005];
ll ans[100005][sz1+5], mn[100005];
vector<int> good;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, t, q;
    cin >> n >> t;
    for (int i=1; i<n; i++)
    {
        int m;
        cin >> m;
        mn[i]=1e18;
        for (int j=0; j<m; j++)
        {
            int l, r;
            cin >> l >> r;
            vec[i].push_back({l, r});
            mn[i]=min(mn[i], (ll)r-l);
        }
    }
    //cout << "here\n";
    for (int i=1; i<n; i++)
    {
        sort(vec[i].begin(), vec[i].end());
        vector<pair<int, ll> > tmp;
        for (pair<int, ll> x:vec[i])
        {
            if (tmp.empty())
                tmp.push_back(x);
            else if (tmp.back().first<x.first)
            {
                while (tmp.size() && tmp.back().second>=x.second)
                    tmp.pop_back();
                tmp.push_back(x);
            }
        }
        vec[i]=tmp;
    }
    //cout << "here\n";
    for (int i=1; i<=n-2; i++)
    {
        //cout << "------i=" << i << '\n';
        int ind=0;
        for (int j=0; j<vec[i].size(); j++)
        {
            while (ind<vec[i+1].size() && vec[i][j].second>vec[i+1][ind].first)
                ind++;
            if (ind==vec[i+1].size())
                nn[i].push_back({0, vec[i+1][0].first+t-vec[i][j].first});
            else
            {
                nn[i].push_back({ind, vec[i+1][ind].first-vec[i][j].first});
                
            }
            //cout << "i j " << i << ' ' << j << ' ' << nn[i][j].second << '\n';
        }
        nxt[i]=nn[i];
    }
    //cout << "here3\n";
    for (int i=2; i<n; i++)
    {
        //cout << "hello\n";
        int ind=vec[i-1].size()-1;
        //cout << "i=" << i << '\n';
        for (int j=vec[i].size()-1; j>=0; j--)
        {
            //cout << "hi " << "j=" << j << '\n';
            while (ind>=0 && vec[i-1][ind].second>vec[i][j].first)
                ind--;
            //cout << j << ' ' << ind << '\n';
            if (ind==-1)
                pp[i].push_back({vec[i-1].size()-1, vec[i][j].first+t-vec[i-1].back().first});
            else
                pp[i].push_back({ind, vec[i][j].first-vec[i-1][ind].first});
        }
        reverse(pp[i].begin(), pp[i].end());
    }
    //cout << "here\n";
    for (int i=1; i<=n-2; i++)
    {
        ans[i][1]=1e18;
        for (int j=0; j<vec[i].size(); j++)
        {
            //cout << j << ' ' << nxt[i][j].first << ' ' << nxt[i][j].second << '\n';
            ans[i][1]=min(ans[i][1], nxt[i][j].second+vec[i+1][nxt[i][j].first].second-vec[i+1][nxt[i][j].first].first);
        }
    }
    //cout << "here\n";
    for (int i=2; i<=sz1; i++)
    {
        for (int j=1; j+i<n; j++)
        {
            vector<pair<int, ll> > tmp;
            ans[j][i]=1e18;
            for (int k=0; k<vec[j].size(); k++)
            {
                int ind=nxt[j][k].first;
                tmp.push_back({nn[j+i-1][ind].first, nxt[j][k].second+nn[j+i-1][ind].second});
                ans[j][i]=min(ans[j][i], tmp[k].second+vec[j+i][tmp[k].first].second-vec[j+i][tmp[k].first].first);
            }
            nxt[j]=tmp;
        }
    }
    //cout << "here\n";
    int ind=-1;
    while (ind+sz1<n)
    {
        for (int i=ind+sz1; i>ind; i--)
        {
            if (vec[i].size()<sz2)
            {
                ind=i;
                good.push_back(ind);
                break;
            }
        }
    }
    //cout << "here\n";
    for (int i=0; i<good.size(); i++)
    {
        int x=good[i];
        //cout << "good " << x << '\n';
        edge[i][x+1]=nn[x];
        for (int j=x+2; j<n; j++)
        {
            for (int k=0; k<vec[x].size(); k++)
            {
                int ind=edge[i][j-1][k].first;
                edge[i][j].push_back({nn[j-1][ind].first, edge[i][j-1][k].second+nn[j-1][ind].second});
                //cout << "edge " << i << ' ' << j << ' ' << k << ' ' << edge[i][j][k].first << ' ' << edge[i][j][k].second << '\n';
            }
        }
        //cout << "hi\n";
        edge[i][x-1]=pp[x];
        for (int j=x-2; j>=1; j--)
        {
            for (int k=0; k<vec[x].size(); k++)
            {
                int ind=edge[i][j+1][k].first;
                edge[i][j].push_back({pp[j+1][ind].first, edge[i][j+1][k].second+pp[j+1][ind].second});
                //cout << "edge " << i << ' ' << j << ' ' << k << ' ' << edge[i][j][k].first << ' ' << edge[i][j][k].second << '\n';
            }
        }
        //cout << "hi\n";
    }
    cin >> q;
    for (int i=1; i<=q; i++)
    {
        int l, r;
        cin >> l >> r;
        r--;
        if (l==r)
        {
            cout << mn[l] << '\n';
            continue;
        }
        if (r-l<=sz1)
        {
            cout << ans[l][r-l] << '\n';
            continue;
        }
        ind=lower_bound(good.begin(), good.end(), l+1)-good.begin();
        ll x=good[ind], ans=1e18;
        for (int j=0; j<vec[x].size(); j++)
            ans=min(ans, edge[ind][l][j].second+edge[ind][r][j].second+vec[r][edge[ind][r][j].first].second-vec[r][edge[ind][r][j].first].first);
        cout << ans << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 17
• Subtask 4: 0 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10