Submission #887093

#	Time	Username	Problem	Language	Result	Execution time	Memory
887093		VerdantGMD	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	794 ms	36560 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n, k;

int maxs[200003];
int mins[200003];
int minjp[200003][20];
int maxjp[200003][20];
int base = n + 1;

void updmax(int a, int b, int x)
{
    a += base - 1;
    b += base + 1;
    while(a/2 != b/2)
    {
        if(a % 2 == 0)
        {
            maxs[a+1] = max(x, maxs[a+1]);
        }
        if(b % 2 == 1)
        {
            maxs[b-1] = max(x, maxs[b-1]);
        }
        a/=2;
        b/=2;
    }
}
void updmin(int a, int b, int x)
{
    a += base - 1;
    b += base + 1;
    while(a/2 != b/2)
    {
        if(a % 2 == 0)
        {
            if(mins[a+1] != 0)
            {
                mins[a+1] = min(x, mins[a+1]);
            }
            else
            {
                mins[a+1] = x;
            }
        }
        if(b % 2 == 1)
        {
            if(mins[b-1] != 0)
            {
                mins[b-1] = min(x, mins[b-1]);
            }
            else
            {
                mins[b-1] = x;
            }
        }
        a/=2;
        b/=2;
    }
}
int querymin(int a)
{
    a += base;
    int minn = 1e9;
    while(a != 0)
    {
        if(mins[a] != 0)
        {
            minn = min(mins[a], minn);
        }
        a/=2;
    }
    return minn;
}
int querymax(int a)
{
    a += base;
    int maxx = -1e9;
    while(a != 0)
    {
        if(maxs[a] != 0)
        {
            maxx = max(maxs[a], maxx);
        }
        a/=2;
    }
    return maxx;
}

void updmaxjp(int a, int it, int val)
{
    a += base;
    while(a != 0)
    {
        if(maxjp[a][it] != 0)
        {
            maxjp[a][it] = max(val, maxjp[a][it]);
        }
        else
        {
            maxjp[a][it] = val;
        }
        a/=2;
    }

}

void updminjp(int a, int it, int val)
{
    a += base;
    while(a != 0)
    {
        if(minjp[a][it] != 0)
        {
            minjp[a][it] = min(val, minjp[a][it]);
        }
        else
        {
            minjp[a][it] = val;
        }
        a/=2;
    }
}

int querymaxjp(int a, int b, int it)
{
    a += base - 1;
    b += base + 1;
    int maxx = -1e9;
    while(a/2 != b/2)
    {
        if(a % 2 == 0)
        {
            if(maxjp[a+1][it] != 0)
            {
                maxx = max(maxx, maxjp[a+1][it]);
            }
        }
        if(b % 2 == 1)
        {
            if(maxjp[b-1][it] != 0)
            {
                maxx = max(maxx, maxjp[b-1][it]);
            }
        }
        a/=2;
        b/=2;
    }
    return maxx;
}

int queryminjp(int a, int b, int it)
{
    a += base - 1;
    b += base + 1;
    int minn = 1e9;
    while(a/2 != b/2)
    {
        if(a % 2 == 0)
        {
            if(minjp[a+1][it] != 0)
            {
                minn = min(minn, minjp[a+1][it]);
            }
        }
        if(b % 2 == 1)
        {
            if(minjp[b-1][it] != 0)
            {
                minn = min(minn, minjp[b-1][it]);
            }
        }
        a/=2;
        b/=2;
    }
    return minn;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    int m;
    cin >> m;
    base = n + 1;
    for(int i = base; i <= base + n; i++)
    {
        mins[i] = i - base;
        maxs[i] = i - base;
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        if(a < b)
        {
            updmax(a, min(a + k-1, b), b);
        }
        else
        {
            updmin(max(a - k+1, b), a, b);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        updminjp(i, 0, querymin(i));
        updmaxjp(i, 0, querymax(i));
        //cout << i << " " << minjp[i+base][0] << " " << maxjp[i+base][0] << endl;
    }
    //cout << endl;
    for(int it = 1; it < 20; it++)
    {
        for (int i = 1; i <= n; i++)
        {
            updmaxjp(i, it, querymaxjp(minjp[i + base][it - 1], maxjp[i + base][it - 1], it - 1));
            updminjp(i, it, queryminjp(minjp[i + base][it - 1], maxjp[i + base][it - 1], it - 1));
            //cout << i << " " << minjp[i+base][it] << " " << maxjp[i+base][it] << endl;
        }

        //cout << endl;
    }

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        if(a == b)
        {
            cout << 0 << endl;
            continue;
        }
        if(a < b)
        {
            int wyn = 0;
            int curl = a;
            int curr = a;
            for(int it = 19; it >= 0; it--)
            {
                if(querymaxjp(curl, curr, it) < b)
                {
                    wyn += pow(2, it);
                    int temp = queryminjp(curl, curr, it);
                    curr = querymaxjp(curl, curr, it);
                    curl = temp;
                }

            }
            if(querymaxjp(curl, curr, 0) >= b)
            {
                cout << wyn + 1 << endl;
            }
            else
            {
                cout << -1 << endl;
            }

        }
        else
        if(a > b)
        {
            int wyn = 0;
            int curl = a;
            int curr = a;
            for(int it = 19; it >= 0; it--)
            {
                if(queryminjp(curl, curr, it) > b)
                {
                    wyn += pow(2, it);
                    int temp = queryminjp(curl, curr, it);
                    curr = querymaxjp(curl, curr, it);
                    curl = temp;
                }

            }
            if(queryminjp(curl, curr, 0) <= b)
            {
                cout << wyn + 1 << endl;
            }
            else
            {
                cout << -1 << endl;
            }

        }
    }

}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13