oj.uz

Submission #800579

# Submission time Handle Problem Language Result Execution time Memory
800579 2023-08-01T16:21:08 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 759 ms 117252 KB 
#include <bits/stdc++.h>
#define int int64_t
#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<<2];

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

int32_t 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 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 6 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Incorrect 5 ms 10196 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 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 6 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Incorrect 5 ms 10196 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 219 ms 108848 KB Output is correct
2 Correct 218 ms 108808 KB Output is correct
3 Correct 247 ms 109852 KB Output is correct
4 Correct 204 ms 108480 KB Output is correct
5 Correct 290 ms 112244 KB Output is correct
6 Correct 269 ms 116328 KB Output is correct
7 Correct 245 ms 114764 KB Output is correct
8 Correct 228 ms 108764 KB Output is correct
9 Correct 177 ms 108580 KB Output is correct
10 Correct 269 ms 112372 KB Output is correct
11 Correct 258 ms 112828 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 113644 KB Output is correct
2 Correct 499 ms 110408 KB Output is correct
3 Correct 450 ms 107184 KB Output is correct
4 Correct 428 ms 105316 KB Output is correct
5 Correct 279 ms 104392 KB Output is correct
6 Correct 370 ms 104012 KB Output is correct
7 Correct 415 ms 111700 KB Output is correct
8 Correct 5 ms 10196 KB Output is correct
9 Correct 12 ms 11884 KB Output is correct
10 Correct 445 ms 114156 KB Output is correct
11 Correct 477 ms 116932 KB Output is correct
12 Correct 550 ms 112680 KB Output is correct
13 Correct 539 ms 117252 KB Output is correct
14 Correct 11 ms 10196 KB Output is correct
15 Incorrect 14 ms 11816 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 10196 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 6 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10196 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Incorrect 5 ms 10196 KB Output isn't correct
9 Halted 0 ms 0 KB -