oj.uz

Submission #636976

# Submission time Handle Problem Language Result Execution time Memory
636976 2022-08-30T22:56:07 Z danikoynov Railway Trip 2 (JOI22_ho_t4) C++14
52 / 100
 2000 ms 36152 KB 
/**
 ____ ____ ____ ____ ____ ____
||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];
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);
        }
    }

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

            cin >> q;
        for (int i = 1; i <= q; i ++)
        {
            int s, t;
            cin >> s >> t;
            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;
    }

    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;
}
/**
6 5
4
3 1
2 4
5 3
4 6
1
3 2

*/

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for (int i = 0; i < rt.size(); i ++)
      |                         ~~^~~~~~~~~~~
Main.cpp:179:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         for (int i = 0; i < lt.size(); i ++)
      |                         ~~^~~~~~~~~~~
Main.cpp:189:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         for (int i = 0; i < frt.size(); i ++)
      |                         ~~^~~~~~~~~~~~
Main.cpp:191:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |             while(pt < frt.size() && frt[pt].a <= frt[i].b)
      |                   ~~~^~~~~~~~~~~~
Main.cpp:201:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         for (int i = 0; i < flt.size(); i ++)
      |                         ~~^~~~~~~~~~~~
Main.cpp:203:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |             while(pt < flt.size() && flt[pt].a >= flt[i].b)
      |                   ~~~^~~~~~~~~~~~
Main.cpp:213:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |             for (int i = 0; i < frt.size(); i ++)
      |                             ~~^~~~~~~~~~~~
Main.cpp:224:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |             for (int i = 0; i < flt.size(); i ++)
      |                             ~~^~~~~~~~~~~~
Main.cpp:223:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  223 |         for (int j = 1; j < maxlog; j ++)
      |         ^~~
Main.cpp:234:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  234 |             cin >> q;
      |             ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19140 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19156 KB Output is correct
4 Correct 9 ms 19152 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19284 KB Output is correct
7 Correct 10 ms 19096 KB Output is correct
8 Correct 9 ms 19152 KB Output is correct
9 Correct 10 ms 19336 KB Output is correct
10 Correct 9 ms 19224 KB Output is correct
11 Correct 10 ms 19028 KB Output is correct
12 Correct 10 ms 19348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19140 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19156 KB Output is correct
4 Correct 9 ms 19152 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19284 KB Output is correct
7 Correct 10 ms 19096 KB Output is correct
8 Correct 9 ms 19152 KB Output is correct
9 Correct 10 ms 19336 KB Output is correct
10 Correct 9 ms 19224 KB Output is correct
11 Correct 10 ms 19028 KB Output is correct
12 Correct 10 ms 19348 KB Output is correct
13 Correct 15 ms 19176 KB Output is correct
14 Correct 16 ms 19156 KB Output is correct
15 Correct 10 ms 19156 KB Output is correct
16 Correct 13 ms 19284 KB Output is correct
17 Correct 12 ms 19284 KB Output is correct
18 Correct 11 ms 19480 KB Output is correct
19 Correct 14 ms 19284 KB Output is correct
20 Correct 15 ms 19276 KB Output is correct
21 Correct 11 ms 19260 KB Output is correct
22 Correct 11 ms 19360 KB Output is correct
23 Correct 11 ms 19156 KB Output is correct
24 Correct 11 ms 19532 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25556 KB Output is correct
2 Correct 44 ms 25420 KB Output is correct
3 Correct 54 ms 26596 KB Output is correct
4 Correct 47 ms 25180 KB Output is correct
5 Correct 170 ms 29552 KB Output is correct
6 Correct 122 ms 33876 KB Output is correct
7 Correct 87 ms 30604 KB Output is correct
8 Correct 91 ms 26316 KB Output is correct
9 Correct 48 ms 24652 KB Output is correct
10 Correct 137 ms 29464 KB Output is correct
11 Correct 87 ms 32580 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 26536 KB Output is correct
2 Correct 103 ms 30920 KB Output is correct
3 Correct 83 ms 35792 KB Output is correct
4 Correct 98 ms 33012 KB Output is correct
5 Correct 100 ms 30776 KB Output is correct
6 Correct 96 ms 31256 KB Output is correct
7 Correct 110 ms 36152 KB Output is correct
8 Correct 115 ms 35008 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1505 ms 29652 KB Output is correct
2 Execution timed out 2100 ms 26988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19140 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19156 KB Output is correct
4 Correct 9 ms 19152 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19284 KB Output is correct
7 Correct 10 ms 19096 KB Output is correct
8 Correct 9 ms 19152 KB Output is correct
9 Correct 10 ms 19336 KB Output is correct
10 Correct 9 ms 19224 KB Output is correct
11 Correct 10 ms 19028 KB Output is correct
12 Correct 10 ms 19348 KB Output is correct
13 Correct 15 ms 19176 KB Output is correct
14 Correct 16 ms 19156 KB Output is correct
15 Correct 10 ms 19156 KB Output is correct
16 Correct 13 ms 19284 KB Output is correct
17 Correct 12 ms 19284 KB Output is correct
18 Correct 11 ms 19480 KB Output is correct
19 Correct 14 ms 19284 KB Output is correct
20 Correct 15 ms 19276 KB Output is correct
21 Correct 11 ms 19260 KB Output is correct
22 Correct 11 ms 19360 KB Output is correct
23 Correct 11 ms 19156 KB Output is correct
24 Correct 11 ms 19532 KB Output is correct
25 Correct 45 ms 25556 KB Output is correct
26 Correct 44 ms 25420 KB Output is correct
27 Correct 54 ms 26596 KB Output is correct
28 Correct 47 ms 25180 KB Output is correct
29 Correct 170 ms 29552 KB Output is correct
30 Correct 122 ms 33876 KB Output is correct
31 Correct 87 ms 30604 KB Output is correct
32 Correct 91 ms 26316 KB Output is correct
33 Correct 48 ms 24652 KB Output is correct
34 Correct 137 ms 29464 KB Output is correct
35 Correct 87 ms 32580 KB Output is correct
36 Correct 53 ms 26536 KB Output is correct
37 Correct 103 ms 30920 KB Output is correct
38 Correct 83 ms 35792 KB Output is correct
39 Correct 98 ms 33012 KB Output is correct
40 Correct 100 ms 30776 KB Output is correct
41 Correct 96 ms 31256 KB Output is correct
42 Correct 110 ms 36152 KB Output is correct
43 Correct 115 ms 35008 KB Output is correct
44 Correct 1505 ms 29652 KB Output is correct
45 Execution timed out 2100 ms 26988 KB Time limit exceeded
46 Halted 0 ms 0 KB -