oj.uz

Submission #800421

# Submission time Handle Problem Language Result Execution time Memory
800421 2023-08-01T14:37:47 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 557 ms 68836 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 = 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);
                        re[a+k].pb(b);
                }
                else
                {
                        ls[a].pb(b);
                        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 = 0; j < n; j++)
                        st[i][j+n] = get(i-1, st[i-1][j+n][0], st[i-1][j+n][1]+1);
                build(i);
        }
        int q;
        cin >> q;
        for (int i = 0; i < q; i++)
        {
                int sp, tp;
                cin >> sp >> tp;
                sp--, tp--;
                if (sp == tp)
                {
                        cout << "0\n";
                        continue;
                }
                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 |= 1<<i;
                        }
                }
                if (dist > INF)
                        cout << "-1\n";
                else
                        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 6 ms 10068 KB Output is correct
5 Correct 6 ms 9956 KB Output is correct
6 Correct 6 ms 10000 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Incorrect 5 ms 10088 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 6 ms 10068 KB Output is correct
5 Correct 6 ms 9956 KB Output is correct
6 Correct 6 ms 10000 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Incorrect 5 ms 10088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 62460 KB Output is correct
2 Correct 205 ms 62376 KB Output is correct
3 Correct 230 ms 63444 KB Output is correct
4 Correct 194 ms 61960 KB Output is correct
5 Incorrect 300 ms 68836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 557 ms 66620 KB Output isn't correct
2 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 6 ms 10068 KB Output is correct
5 Correct 6 ms 9956 KB Output is correct
6 Correct 6 ms 10000 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Incorrect 5 ms 10088 KB Output isn't correct
9 Halted 0 ms 0 KB -