Submission #636974

#	Time	Username	Problem	Language	Result	Execution time	Memory
636974		danikoynov	Railway Trip 2 (JOI22_ho_t4)	C++14	16 / 100	2071 ms	30548 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 = 1e5 + 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];
void solve()
{
    cin >> n >> k;
    cin >> m;

    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
        {
            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);
        }
    }

    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));
        }
    }

    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));
    }


    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int s, t;
        cin >> s >> t;
        int ans = solve_query(s, t);
        cout << ans << endl;
    }
}

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

*/

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