Submission #1187932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187932		dragst	Escape Route 2 (JOI24_escape2)	C++20	0 / 100	3093 ms	31760 KiB

Main

#include <bits/stdc++.h>
#define pll pair<long long, long long>
using namespace std;

struct thing
{
    long long nxt, day;
};

thing jump[100005][20], p;
long long l[100005], r[100005], id[100005], mn[100005];
pll a[100005];

bool sortt(long long x, long long y) {return a[x]<a[y];}

bool sorttt(long long x, long long y) {return a[x].second<a[y].second;}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, T, q, i, j, k=1, h;
    cin >> n >> T;
    for (i=1; i<n; i++)
    {
        cin >> j;
        l[i]=r[i-1]+1; r[i]=l[i]+j-1; h=T-1;
        while (j--)
        {
            cin >> a[k].first >> a[k].second;
            if (a[k].second<h) {mn[i]=k; h=a[k].second;};
            id[k]=k; k++;
        };
    };
    for (i=n-1; i>=1; i--)
    {
        if (i<n-1) {sort(id+l[i+1], id+r[i+1]+1, sortt);}
        else {continue;};
        sort(id+l[i], id+r[i]+1, sorttt);
        k=r[i+1]; p={mn[i+1], 1LL};
        for (j=r[i]; j>=l[i]; j--)
        {
            while (k>=l[i+1] && a[id[k]].first>=a[id[j]].second)
            {
                if (p.day==1) {p={id[k], 0LL};}
                else if (a[id[k]].second<a[p.nxt].second) {p={id[k], p.day};};
                k--;
            };
            jump[id[j]][0]=p;
            for (h=1; i+(1LL<<h)<n; h++)
            {
                jump[id[j]][h]={jump[jump[id[j]][h-1].nxt][h-1].nxt, jump[id[j]][h-1].day+jump[jump[id[j]][h-1].nxt][h-1].day};
            };
        };
    };
    cin >> q;
    while (q--)
    {
        cin >> i >> j;
        long long ans=T*n;
        k=j-i-1;
        for (long long x=l[i]; x<=r[i]; x++)
        {
            thing xx={x, 0LL};
            for (h=0; (1LL<<h)<=k; h++)
            {
                if (k&(1LL<<h)) {xx={jump[xx.nxt][h].nxt, xx.day+jump[xx.nxt][h].day};};
            };
            ans=min(ans, a[xx.nxt].second-a[x].first+T*xx.day);
        };
        cout << ans << "\n";
    };
}

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