oj.uz

Submission #800568

# Submission time Handle Problem Language Result Execution time Memory
800568 2023-08-01T16:15:17 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 528 ms 54984 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 = 4e5;
constexpr static int MXLOG = 21;

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 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9864 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Incorrect 5 ms 9940 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9864 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Incorrect 5 ms 9940 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 173 ms 47624 KB Output is correct
2 Correct 172 ms 47528 KB Output is correct
3 Correct 194 ms 48472 KB Output is correct
4 Correct 157 ms 47180 KB Output is correct
5 Correct 236 ms 50332 KB Output is correct
6 Correct 225 ms 54984 KB Output is correct
7 Correct 208 ms 53448 KB Output is correct
8 Correct 159 ms 47948 KB Output is correct
9 Correct 134 ms 47116 KB Output is correct
10 Correct 226 ms 50552 KB Output is correct
11 Correct 207 ms 51164 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 50548 KB Output is correct
2 Correct 367 ms 49088 KB Output is correct
3 Correct 308 ms 45956 KB Output is correct
4 Correct 334 ms 43996 KB Output is correct
5 Correct 214 ms 43120 KB Output is correct
6 Correct 279 ms 42776 KB Output is correct
7 Correct 308 ms 50448 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 13 ms 10580 KB Output is correct
10 Correct 352 ms 51080 KB Output is correct
11 Correct 389 ms 54472 KB Output is correct
12 Correct 430 ms 50464 KB Output is correct
13 Correct 423 ms 54416 KB Output is correct
14 Correct 5 ms 9940 KB Output is correct
15 Incorrect 11 ms 10580 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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