Submission #1092780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092780		modwwe	Escape Route 2 (JOI24_escape2)	C++17	0 / 100	60 ms	42120 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}

void phongbeo();
const int inf = 1e17;
const int mod2 = 1e9 + 9;
const int  mod1 = 998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};

int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, l, r, mid, l2, r2, center;
int  i, s10, s12,k1,k2,s11;
int kk;
int el = 19;
main()
{
    //fin(task);
    //fou(task);
     NHP
    /// cin>>s1;
///modwwe
    phongbeo();
    // checktime
}
int S=50;
int s,t;
vector<ib> a[100001];
int b[100001];
vector<int> c[100001];
ib d[100001];
ib st[17][100001];
vector<int> vv;
vector<ib> v[100001];
vector<int> dp[318];
int ans[100001];
bool f[100001];
int pos[100001];
int prefix_b[100001];
int rig[100001];
bool cmp(ib a,ib b)
{
    return a.a<b.a;
}
int get(int l,int j,int r)
{
    s=r-l-1;
    s3=c[l][j];
    s4=0;/// 3->4->0
    for(int f=0; f<17; f++)
        if(bit(s,f))
            s4+=st[f][s3].b,s3=st[f][s3].a;
    return s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a;
}
void setup()
{
    s2=n+1;
    dem=0;
    for(int i=n-1; i>=1; --i)
    {
        if(b[i]<=S)
            s2=i;
        if(s2!=i&&f[i]&&s2!=n+1)
        {
            s3=s2-i;
            pos[i]=dem++;
            dp[dem].resize(330);
            rig[i]=s2;
            for(int j=1; j<=319; j++)
                dp[dem][j]=inf;
            for(int j=1; j<=b[i]; j++)
            {
                s4=c[i][j];
                s=0;
                for(int j=17; j>=0; --j)
                    if(bit(s3,j))
                        s+=st[j][s4].b,s4=st[j][s4].a;
                dp[dem][s4-prefix_b[s2-1]]=min(s,dp[dem][s4-prefix_b[s2-1]]);
            }
        }
    }
}
void phongbeo()
{
    cin>>n>>t;
    for(int i=1; i<n; i++)
    {
        cin>>k;
        b[i]=k;
        a[i].resize(k+1);
        c[i].resize(k+1);
        prefix_b[i]=b[i]+prefix_b[i-1];
        s9+=k;
        for(int j=1; j<=k; j++)
            cin>>a[i][j].a>>a[i][j].b,c[i][j]=++dem,d[dem]= {i,j};
        sort(a[i].begin()+1,a[i].end(),cmp);
        for(int j=k-1; j>=1; --j)
            a[i][j].b=min(a[i][j].b,a[i][j+1].b);
    }

    for(int i=1; i<n-1; i++)
    {
        vv.clear();
        for(int j=1; j<=b[i+1]; j++)
            vv.pb(a[i+1][j].a);
        for(int j=1; j<=b[i]; j++)
        {
            if(a[i][j].b>vv.back())
            {
                s3=vv[0]+t-a[i][j].a;
                st[0][c[i][j]]= {c[i+1][1],s3};
            }
            else
            {
                s2=lower_bound(vv.begin(),vv.end(),a[i][j].b)-vv.begin()+1;
                s3=a[i+1][s2].a-a[i][j].a;
                st[0][c[i][j]]= {c[i+1][s2],s3};
            }
        }
    }

    for(int i=1; i<17; i++)
        for(int j=1; j<=s9; j++)
            st[i][j].a=st[i-1][st[i-1][j].a].a,
                    st[i][j].b=st[i-1][j].b+st[i-1][st[i-1][j].a].b;
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r;
        v[l].pb({r,i});
        f[l]=1;
        /*  if(l==r)
          {
              cout<<0,down continue;
          }
          for(int j=1; j<=b[l]; j++)
          {
              s=r-l-1;
              s3=c[l][j];
              s4=0;/// 3->4->0
              for(int f=0; f<17; f++)
                  if(bit(s,f))
                      s4+=st[f][s3].b,s3=st[f][s3].a;
              if(j==1)s5=s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a;
              else s5=min(s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a,s5);
          }
          cout<<s5,down*/
    }
    setup();
    for(int i=1; i<=n; i++)
    {
        for(auto x:v[i])
        {
            s5=inf;
            if(b[i]<=S||x.a<=rig[i])
            {
                for(int j=1; j<=b[i]; j++)
                {
                    r=x.a;
                    l=i;
                    s=r-l-1;
                    s3=c[l][j];
                    s4=0;/// 3->4->0
                    for(int f=0; f<17; f++)
                        if(bit(s,f))
                            s4+=st[f][s3].b,s3=st[f][s3].a;
                    s5=min(s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a,s5);
                }
            }
            else
            {
                l=rig[i];
                for(int j=1; j<=b[l]; j++)
                {
                    if(dp[pos[i]][c[l][j]-prefix_b[l-1]]==inf) continue;
                    r=x.a;
                    s=r-l-1;
                    s3=c[l][j];
                    s4=0;/// 3->4->0
                    for(int f=0; f<17; f++)
                        if(bit(s,f))
                            s4+=st[f][s3].b,s3=st[f][s3].a;
                    s5=min(s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a+dp[pos[i]][c[l][j]-prefix_b[l-1]],s5);
                }
            }
            ans[x.b]=s5;
        }
        s2=1;
    }
    for(int i=1; i<=m; i++)
        cout<<ans[i],down
    }

Compilation message (stderr)

Main.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~

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