oj.uz

Submission #800574

# Submission time Handle Problem Language Result Execution time Memory
800574 2023-08-01T16:17:17 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 657 ms 69172 KB 
#include <bits/stdc++.h>
#define mp(x...) array<int, 2>({x})
#define pb push_back
using namespace std;

constexpr static int MXSIZE = 1e5;
constexpr static int INF = 1e8;
constexpr static int MXLOG = 30;

int n, k;
vector<int> rs[MXSIZE], re[MXSIZE], ls[MXSIZE], le[MXSIZE];
array<int, 2> st[MXLOG][MXSIZE<<1];

array<int, 2> merge(array<int, 2> a, array<int, 2> b)
{
        return mp(min(a[0], b[0]), max(a[1], b[1]));
}

void build(int i)
{
        for (int j = n-1; j >= 0; j--) st[i][j] = merge(st[i][j<<1], st[i][(j<<1)|1]);
}

array<int, 2> get(int i, int l, int r)
{
        array<int, 2> res = {INF, -INF};
        for (l+=n,r+=n;r>l;r>>=1,l>>=1)
        {
                if (l&1) res = merge(res, st[i][l++]);
                if (r&1) res = merge(res, st[i][--r]);
        }
        return res;
}

int main()
{
        cin >> n >> k;
        int m;
        cin >> m;
        for (int i = 0; i < m; i++)
        {
                int a, b;
                cin >> a >> b;
                a--, b--;
                if (a < b)
                {
                        rs[a].pb(b);
                        if (a + k < n)
                                re[a+k].pb(b);
                }
                else
                {
                        ls[a].pb(b);
                        if (a - k >= 0)
                                le[a-k].pb(b);
                }
        }
        multiset<int> s;
        for (int i = 0; i < n; i++)
        {
                for (int j : rs[i])
                        s.insert(j);
                for (int j : re[i])
                        s.erase(j);
                if (s.empty())
                        st[0][i+n][1] = i;
                else
                        st[0][i+n][1] = *s.rbegin();
        }
        s.clear();
        for (int i = n-1; i >= 0; i--)
        {
                for (int j : ls[i])
                        s.insert(j);
                for (int j : le[i])
                        s.erase(j);
                if (s.empty())
                        st[0][i+n][0] = i;
                else
                        st[0][i+n][0] = *s.begin();
        }
        build(0);
        for (int i = 1; i < MXLOG; i++)
        {
                for (int j = n; j < n*2; j++)
                        st[i][j] = get(i-1, st[i-1][j][0], st[i-1][j][1]+1);
                build(i);
        }
        int q;
        cin >> q;
        for (int j = 0; j < q; j++)
        {
                int sp, tp;
                cin >> sp >> tp;
                sp--, tp--;
                int dist = 0, l = sp, r = sp;
                for (int i = MXLOG-1; i >= 0; i--)
                {
                        auto [nl, nr] = get(i, l, r+1);
                        if (nl > tp || nr < tp)
                        {
                                l = nl, r = nr;
                                dist = dist|(1<<i);
                        }
                }
                if (dist > INF)
                {
                        cout << "-1\n";
                }
                else
                {
                        auto [nl, nr] = get(0, l, r+1);
                        assert(nl <= tp && tp <= nr);
                        cout << (dist+1) << "\n";
                }
        }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10068 KB Output is correct
5 Correct 7 ms 10068 KB Output is correct
6 Correct 5 ms 10068 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 4 ms 10068 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10068 KB Output is correct
5 Correct 7 ms 10068 KB Output is correct
6 Correct 5 ms 10068 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 4 ms 10068 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 61744 KB Output is correct
2 Correct 201 ms 61516 KB Output is correct
3 Correct 223 ms 62680 KB Output is correct
4 Correct 191 ms 61264 KB Output is correct
5 Correct 256 ms 64412 KB Output is correct
6 Correct 251 ms 69172 KB Output is correct
7 Correct 217 ms 67484 KB Output is correct
8 Correct 188 ms 61912 KB Output is correct
9 Correct 166 ms 61256 KB Output is correct
10 Correct 255 ms 64632 KB Output is correct
11 Correct 244 ms 65392 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 61588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 64724 KB Output is correct
2 Correct 463 ms 63296 KB Output is correct
3 Correct 393 ms 60024 KB Output is correct
4 Correct 388 ms 58060 KB Output is correct
5 Correct 259 ms 57208 KB Output is correct
6 Correct 349 ms 56816 KB Output is correct
7 Correct 391 ms 64548 KB Output is correct
8 Correct 5 ms 10068 KB Output is correct
9 Correct 12 ms 10964 KB Output is correct
10 Correct 416 ms 65256 KB Output is correct
11 Correct 487 ms 68576 KB Output is correct
12 Correct 506 ms 64432 KB Output is correct
13 Correct 519 ms 68532 KB Output is correct
14 Correct 5 ms 10068 KB Output is correct
15 Incorrect 13 ms 10860 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10068 KB Output is correct
5 Correct 7 ms 10068 KB Output is correct
6 Correct 5 ms 10068 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 4 ms 10068 KB Output isn't correct
9 Halted 0 ms 0 KB -