Submission #637051

#	Time	Username	Problem	Language	Result	Execution time	Memory
637051		danikoynov	Railway Trip 2 (JOI22_ho_t4)	C++14	87 / 100	2074 ms	52416 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

struct road
{
    int a, b;
} r[maxn];

struct interval
{
    int l, r, idx;

    interval(int _l = 0, int _r = 0, int _idx = 0)
    {
        l = _l;
        r = _r;
        idx = _idx;
    }

    bool operator < (const interval &it) const
    {
        return make_pair(l, r) < make_pair(it.l, it.r);
    }
};

int n, k, m, q;

bool on_train(int pos, int idx)
{
    if (r[idx].a < r[idx].b)
    {
        return (pos >= r[idx].a && pos <= r[idx].a + k - 1);
    }
    else
    {
        return (pos >= r[idx].a - k + 1 && pos <= r[idx].a);
    }
}

int to_left[maxn], to_right[maxn];

int solve_query(int s, int t)
{
    int lf = s, rf = s, len = 0, nlf = min(lf, to_left[lf]), nrf = max(rf, to_right[rf]);
    while(true)
    {
        if (lf <= t && rf >= t)
            return len;

        if (nlf == lf && rf == nrf)
            break;

        int tlf = nlf, trf = nrf;
        for (int j = rf + 1; j <= nrf; j ++)
        {
            tlf = min(tlf, to_left[j]);
            trf = max(trf, to_right[j]);
        }
        for (int j = nlf; j < lf; j ++)
        {
            tlf = min(tlf, to_left[j]);
            trf = max(trf, to_right[j]);
        }

        lf = nlf;
        rf = nrf;
        len ++;
        nlf = tlf;
        nrf = trf;
    }

    return -1;
}
vector < int > tr_add[maxn], tr_rem[maxn];
vector < int > tl_add[maxn], tl_rem[maxn];

bool cmp_rt(road it1, road it2)
{
    if (it1.a < it2.a)
        return true;
    if (it1.a > it2.a)
        return false;
    return it1.b > it2.b;
}

bool cmp_lt(road it1, road it2)
{
    if (it1.a > it2.a)
        return true;
    if (it1.a < it2.a)
        return false;
    return it1.b < it2.b;
}

const int maxlog = 20;
int dp[maxlog][maxn], fp[maxlog][maxn], lg[maxn];
pair < int, int > ask[maxn];

int query(int l, int r)
{
    if (l > r)
        return 0;
    int len = lg[r - l + 1] - 1, ans = fp[len][l];
    if (to_right[fp[len][r - (1 << len) + 1]] > to_right[ans])
        ans = fp[len][r - (1 << len) + 1];
    return ans;
}
void solve()
{
    cin >> n >> k;
    cin >> m;
    bool up = true;
    for (int i = 1; i <= n; i ++)
    {
        to_left[i] = n + 1;
        to_right[i] = 0;
    }

    for (int i = 1; i <= m; i ++)
    {
        cin >> r[i].a >> r[i].b;
        if (r[i].a < r[i].b)
        {
            if (r[i].a < n)
            {
                tr_add[r[i].a].push_back(r[i].b);
                tr_rem[min(n, r[i].a + k - 1)].push_back(r[i].b);

            }
            ///for (int j = r[i].a; j <= min(n, r[i].a + k - 1); j ++)
            ///to_right[j] = max(to_right[j], r[i].b);
        }
        else
        {
            up = false;
            if (r[i].a > 1)
            {
                tl_add[r[i].a].push_back(r[i].b);
                tl_rem[max(1, r[i].a - k + 1)].push_back(r[i].b);
            }
            ///for (int j = r[i].a; j >= max(1, r[i].a - k + 1); j --)
            /// to_left[j] = min(to_left[j], r[i].b);
        }
    }

    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        cin >> ask[i].first >> ask[i].second;
        if (ask[i].second < ask[i].first)
            up = false;
    }

        multiset < int > st;
    for (int i = 1; i <= n; i ++)
    {
        for (int v : tr_add[i])
        {
            ///cout << "add " << v << endl;
            st.insert(v);
        }

        if (!st.empty())
            to_right[i] = *st.rbegin();

        for (int v : tr_rem[i])
        {
            ///cout << "rem " << v << endl;
            st.erase(st.find(v));
        }
    }

    if (up)
    {
        for (int i = 1; i <= n; i ++)
            fp[0][i] = i;

        for (int j = 1; j < maxlog; j ++)
            for (int i = 1; i <= n - (1 << j) + 1; i ++)
        {
            fp[j][i] = fp[j - 1][i];
            if (to_right[fp[j - 1][i + (1 << (j - 1))]] > to_right[fp[j][i]])
                fp[j][i] = fp[j - 1][i + (1 << (j - 1))];
        }
        for (int i = 1; i <= n; i ++)
            lg[i] = lg[i / 2] + 1;

        /**for (int i = 1; i <= n; i ++)
            cout << to_right[i] << " ";
        cout << endl;*/

        for (int i = 1; i <= n; i ++)
        {
            int mx = query(i + 1, to_right[i]);
            if (to_right[mx] == 0)
                dp[0][i] = -1;
            else
                dp[0][i] = mx;
        }

        for (int j = 1; j < maxlog; j ++)
        {
            for (int i = 1; i <= n; i ++)
            {
                if (dp[j - 1][i] == -1)
                {
                    dp[j][i] = -1;
                    continue;
                }
                dp[j][i] = dp[j - 1][dp[j - 1][i]];
            }
        }

        /**for (int j = 0; j < 4; j ++, cout << endl)
            for (int i = 1; i <= n; i ++)
            cout << dp[j][i] << " ";*/

        for (int i = 1; i <= q; i ++)
        {
            int s, t;
            s = ask[i].first;
            t = ask[i].second;
            int jump = 0;
            if (to_right[s] >= t)
            {
                cout << 1 << endl;
                continue;
            }
            for (int bit = maxlog - 1; bit >= 0; bit --)
            {
                if (dp[bit][s] == -1 || to_right[dp[bit][s]] >= t)
                    continue;
                jump = jump + (1 << bit);
                s = dp[bit][s];
            }

            /**if (to_right[s] >= t)
            {
                cout << jump + 1 << endl;
                continue;
            }
            cout << dp[0][s] << endl;*/
            if (dp[0][s] == -1)
            {
                cout << -1 << endl;
                continue;
            }
            cout << jump + 2 << endl;
        }

        /**
        12 1
5
1 7
10 12
3 5
8 10
5 9
1
3 12
*/
        return;
    }

    if (k == n - 1)
    {
        vector < road > rt, lt, frt, flt;
        for (int i = 1; i <= m; i ++)
        {
            if (r[i].a < r[i].b)
                rt.push_back(r[i]);
            else
                lt.push_back(r[i]);
        }

        sort(lt.begin(), lt.end(), cmp_lt);
        sort(rt.begin(), rt.end(), cmp_rt);

        int to_r = 0;
        for (int i = 0; i < rt.size(); i ++)
        {
            if (rt[i].b > to_r)
            {
                to_r = rt[i].b;
                frt.push_back(rt[i]);
            }
        }

        int to_l = n + 1;
        for (int i = 0; i < lt.size(); i ++)
        {
            if (lt[i].b < to_l)
            {
                to_l = lt[i].b;
                flt.push_back(lt[i]);
            }
        }

        int pt = 0;
        for (int i = 0; i < frt.size(); i ++)
        {
            while(pt < frt.size() && frt[pt].a <= frt[i].b)
                pt ++;
            pt --;
            if (pt == i)
                dp[0][i] = -1;
            else
                dp[0][i] = pt;
        }

        pt = 0;
        for (int i = 0; i < flt.size(); i ++)
        {
            while(pt < flt.size() && flt[pt].a >= flt[i].b)
                pt ++;
            pt --;
            if (pt == i)
                fp[0][i] = -1;
            else
                fp[0][i] = pt;
        }

        for (int j = 1; j < maxlog; j ++)
            for (int i = 0; i < frt.size(); i ++)
            {
                if (dp[j - 1][i] == -1)
                {
                    dp[j][i] = -1;
                    continue;
                }
                dp[j][i] = dp[j - 1][dp[j - 1][i]];
            }

        for (int j = 1; j < maxlog; j ++)
            for (int i = 0; i < flt.size(); i ++)
            {
                if (fp[j - 1][i] == -1)
                {
                    fp[j][i] = -1;
                    continue;
                }
                fp[j][i] = fp[j - 1][fp[j - 1][i]];
            }

        for (int i = 1; i <= q; i ++)
        {
            int s, t;
            s = ask[i].first;
            t = ask[i].second;
            if (s < t)
            {
                if (frt.size() == 0)
                {
                    cout << -1 << endl;
                    continue;
                }
                int lb = 0, rb = frt.size() - 1;
                while(lb <= rb)
                {
                    int mb = (lb + rb) / 2;
                    if (frt[mb].a > s)
                        rb = mb - 1;
                    else
                        lb = mb + 1;
                }
                if (rb == -1 || frt[rb].a > s || frt[rb].b < s)
                {
                    cout << -1 << endl;
                    continue;
                }
                if (frt[rb].b >= t)
                {
                    cout << 1 << endl;
                    continue;
                }
                int jump = 0, pos = rb;

                for (int bit = maxlog - 1; bit >= 0; bit --)
                {
                    int id = dp[bit][pos];
                    if (id == -1 || frt[id].b >= t)
                        continue;
                    jump = jump + (1 << bit);
                    pos = id;
                }

                if (dp[0][pos] == -1)
                {
                    cout << -1 << endl;
                    continue;
                }
                cout << jump + 2 << endl;

            }
            else
            {
                if (flt.size() == 0)
                {
                    cout << -1 << endl;
                    continue;
                }
                int lb = 0, rb = flt.size() - 1;
                while(lb <= rb)
                {
                    int mb = (lb + rb) / 2;
                    if (flt[mb].a < s)
                        rb = mb - 1;
                    else
                        lb = mb + 1;
                }
                ///cout << flt[rb].a << " : " << flt[rb].b << endl;
                if (rb == -1 || flt[rb].b > s || flt[rb].a < s)
                {
                    cout << -1 << endl;
                    continue;
                }
                if (flt[rb].b <= t)
                {
                    cout << 1 << endl;
                    continue;
                }
                int jump = 0, pos = rb;
                for (int bit = maxlog - 1; bit >= 0; bit --)
                {
                    int id = fp[bit][pos];
                    if (id == -1 || flt[id].b <= t)
                        continue;
                    jump = jump + (1 << bit);
                    pos = id;
                }
                if (fp[0][pos] == -1)
                    {
                        cout << -1 << endl;
                        continue;
                    }
                cout << jump + 2 << endl;

            }
        }
        return;
    }



    st.clear();
    for (int i = n; i > 0; i --)
    {
        for (int v : tl_add[i])
            st.insert(v);

        if (!st.empty())
            to_left[i] = *st.begin();

        for (int v : tl_rem[i])
            st.erase(st.find(v));
    }


    for (int i = 1; i <= q; i ++)
    {
        int s, t;
        s = ask[i].first;
        t = ask[i].second;
        int ans = solve_query(s, t);
        cout << ans << endl;
    }
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
6 5
4
3 1
2 4
5 3
4 6
1
3 2

*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:300:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  300 |         for (int i = 0; i < rt.size(); i ++)
      |                         ~~^~~~~~~~~~~
Main.cpp:310:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  310 |         for (int i = 0; i < lt.size(); i ++)
      |                         ~~^~~~~~~~~~~
Main.cpp:320:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  320 |         for (int i = 0; i < frt.size(); i ++)
      |                         ~~^~~~~~~~~~~~
Main.cpp:322:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  322 |             while(pt < frt.size() && frt[pt].a <= frt[i].b)
      |                   ~~~^~~~~~~~~~~~
Main.cpp:332:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |         for (int i = 0; i < flt.size(); i ++)
      |                         ~~^~~~~~~~~~~~
Main.cpp:334:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  334 |             while(pt < flt.size() && flt[pt].a >= flt[i].b)
      |                   ~~~^~~~~~~~~~~~
Main.cpp:344:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  344 |             for (int i = 0; i < frt.size(); i ++)
      |                             ~~^~~~~~~~~~~~
Main.cpp:355:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  355 |             for (int i = 0; i < flt.size(); i ++)
      |                             ~~^~~~~~~~~~~~

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