oj.uz

Submission #203006

# Submission time Handle Problem Language Result Execution time Memory
203006 2020-02-19T02:13:10 Z gs18115 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 432 ms 111096 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct seg
{
    pi t[400010];
    void si(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            t[n]=pi(p,x);
            return;
        }
        int m=(s+e)/2;
        if(x>m)
            si(n*2+1,m+1,e,x,p);
        else
            si(n*2,s,m,x,p);
        t[n]=max(t[n*2],t[n*2+1]);
        return;
    }
    pi sq(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return pi(-inf,0);
        if(S<=s&&e<=E)
            return t[n];
        int m=(s+e)/2;
        return max(sq(n*2,s,m,S,E),sq(n*2+1,m+1,e,S,E));
    }
}st;
int tct=2;
int dp[200010];
int spd[200010][20][2][2];
int spa[200010][20],kth[200010];
inline void app(pi&x,int y[2][2])
{
    pi t=x;
    x.fi=min(t.fi+y[0][0],t.se+y[1][0]);
    x.se=min(t.fi+y[0][1],t.se+y[1][1]);
    return;
}
inline void merge(int r[2][2],int x[2][2],int y[2][2])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            r[i][j]=min(x[i][0]+y[0][j],x[i][1]+y[1][j]);
    return;
}
int lcq(int x,int y,bool rr)
{
    pi ld(0,1);
    pi rd(0,1);
    if(rr)
        rd=pi(1,0);
    if(dp[x]<dp[y])
        swap(x,y),swap(ld,rd);
    for(int i=0;i<20;i++)
        if((dp[x]-dp[y])>>i&1)
            app(ld,spd[x][i]),x=spa[x][i];
    if(x==y)
        return 0;
    for(int i=20;i-->0;)
        if(spa[x][i]!=spa[y][i])
            app(ld,spd[x][i]),app(rd,spd[y][i]),x=spa[x][i],y=spa[y][i];
    if(kth[x]>kth[y])
        swap(x,y),swap(ld,rd);
    return min(ld.se+rd.fi+kth[y]-kth[x]-1,ld.fi+rd.se+spd[x][0][0][0]+spd[y][0][1][0])-1;
}
vector<int>adj[200010];
int node[100010];
int n,k,q;
void maketree(int n,int s,int e)
{
    if(s>e-2)
    {
        node[s]=n;
        return;
    }
    pi t=st.sq(1,1,::n,s+1,e-1);
    vector<int>v;
    vector<pi>itv;
    v.eb(t.se);
    while(v.back()>s+1)
    {
        pi t2=st.sq(1,1,::n,s+1,v.back()-1);
        if(t2.fi!=t.fi)
            break;
        v.eb(t2.se);
    }
    reverse(all(v));
    itv.eb(s,v[0]);
    for(int i=1;i<(int)v.size();i++)
        itv.eb(v[i-1],v[i]);
    itv.eb(v.back(),e);
    int sz=(int)itv.size();
    for(int i=0;i<sz;i++)
    {
        int t=tct++;
        adj[n].eb(t);
        kth[t]=i;
        spa[t][0]=n;
        dp[t]=dp[n]+1;
        for(int j=0;j<2;j++)
        {
            spd[t][0][j][0]=i+j,spd[t][0][j][1]=sz-i-j;
            for(int k=0;k<2;k++)
                spd[t][0][j][k]=min(spd[t][0][j][k],spd[t][0][j][k^1]+1);
        }
    }
    for(int i=0;i<sz;i++)
        maketree(adj[n][i],itv[i].fi,itv[i].se);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>q;
    if(n<3)
    {
        for(int i=0;i<q;i++)
            cout<<"0\n";
        cout.flush();
        return 0;
    }
    for(int i=0;i++<n;)
    {
        int t;
        cin>>t;
        st.si(1,1,n,i,t);
    }
    maketree(1,1,n);
    if(st.sq(1,1,n,2,n-1).fi==k)
        for(int k=0;k<(int)adj[1].size();k++)
            for(int i=0;i<2;i++)
                spd[adj[1][k]][0][i][0]=k+i,spd[adj[1][k]][0][i][1]=(int)adj[1].size()-k-i;
    for(int i=0;i<19;i++)
        for(int j=1;j<tct;j++)
            spa[j][i+1]=spa[spa[j][i]][i],merge(spd[j][i+1],spd[j][i],spd[spa[j][i]][i]);
    while(q-->0)
    {
        int l,r;
        cin>>l>>r;
        if(l>r)
            swap(l,r);
        if(r==n)
            cout<<lcq(node[l],node[r-1],1);
        else
            cout<<lcq(node[l],node[r],0);
        cout<<'\n';
    }
    cout.flush();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 8 ms 5112 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 8 ms 5112 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5880 KB Output is correct
2 Correct 203 ms 78232 KB Output is correct
3 Correct 215 ms 83116 KB Output is correct
4 Correct 227 ms 87036 KB Output is correct
5 Correct 225 ms 88568 KB Output is correct
6 Correct 233 ms 90488 KB Output is correct
7 Correct 236 ms 91000 KB Output is correct
8 Correct 127 ms 49768 KB Output is correct
9 Correct 183 ms 71160 KB Output is correct
10 Correct 163 ms 62576 KB Output is correct
11 Correct 193 ms 69880 KB Output is correct
12 Correct 191 ms 70008 KB Output is correct
13 Correct 199 ms 69832 KB Output is correct
14 Correct 189 ms 69880 KB Output is correct
15 Correct 190 ms 70008 KB Output is correct
16 Correct 199 ms 70136 KB Output is correct
17 Correct 233 ms 91128 KB Output is correct
18 Correct 236 ms 91000 KB Output is correct
19 Correct 239 ms 91384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 82424 KB Output is correct
2 Correct 304 ms 79900 KB Output is correct
3 Correct 319 ms 82936 KB Output is correct
4 Correct 321 ms 83576 KB Output is correct
5 Correct 316 ms 83832 KB Output is correct
6 Correct 320 ms 84472 KB Output is correct
7 Correct 312 ms 84768 KB Output is correct
8 Correct 252 ms 60436 KB Output is correct
9 Correct 200 ms 50244 KB Output is correct
10 Correct 205 ms 50244 KB Output is correct
11 Correct 199 ms 50376 KB Output is correct
12 Correct 198 ms 50376 KB Output is correct
13 Correct 204 ms 50244 KB Output is correct
14 Correct 207 ms 50448 KB Output is correct
15 Correct 207 ms 50808 KB Output is correct
16 Correct 256 ms 58276 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 92536 KB Output is correct
2 Correct 333 ms 92664 KB Output is correct
3 Correct 325 ms 92280 KB Output is correct
4 Correct 331 ms 92536 KB Output is correct
5 Correct 202 ms 50248 KB Output is correct
6 Correct 334 ms 72988 KB Output is correct
7 Correct 328 ms 72952 KB Output is correct
8 Correct 273 ms 64088 KB Output is correct
9 Correct 336 ms 71544 KB Output is correct
10 Correct 340 ms 71672 KB Output is correct
11 Correct 335 ms 71544 KB Output is correct
12 Correct 324 ms 71548 KB Output is correct
13 Correct 336 ms 71672 KB Output is correct
14 Correct 403 ms 90872 KB Output is correct
15 Correct 431 ms 98808 KB Output is correct
16 Correct 432 ms 111096 KB Output is correct
17 Correct 385 ms 81656 KB Output is correct
18 Correct 391 ms 82468 KB Output is correct
19 Correct 390 ms 82764 KB Output is correct
20 Correct 354 ms 76536 KB Output is correct
21 Correct 337 ms 92472 KB Output is correct
22 Correct 330 ms 92536 KB Output is correct
23 Correct 347 ms 92664 KB Output is correct