oj.uz

답안 #800563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800563 2023-08-01T16:12:16 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 521 ms 54980 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 i = 0; i < q; i++)
        {
                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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9972 KB Output is correct
4 Correct 7 ms 9952 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 5 ms 9960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9972 KB Output is correct
4 Correct 7 ms 9952 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 5 ms 9960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 47568 KB Output is correct
2 Correct 177 ms 47508 KB Output is correct
3 Correct 207 ms 48492 KB Output is correct
4 Correct 154 ms 47296 KB Output is correct
5 Correct 269 ms 50276 KB Output is correct
6 Correct 230 ms 54980 KB Output is correct
7 Correct 200 ms 53508 KB Output is correct
8 Correct 192 ms 47992 KB Output is correct
9 Correct 136 ms 47092 KB Output is correct
10 Correct 257 ms 50596 KB Output is correct
11 Correct 227 ms 51172 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 241 ms 47480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 521 ms 50652 KB Output is correct
2 Correct 388 ms 49136 KB Output is correct
3 Correct 352 ms 45956 KB Output is correct
4 Correct 321 ms 43964 KB Output is correct
5 Correct 215 ms 42964 KB Output is correct
6 Correct 322 ms 42796 KB Output is correct
7 Correct 337 ms 50480 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 11 ms 10620 KB Output is correct
10 Correct 356 ms 51084 KB Output is correct
11 Correct 434 ms 54568 KB Output is correct
12 Correct 435 ms 50476 KB Output is correct
13 Correct 505 ms 54456 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Incorrect 16 ms 10576 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9972 KB Output is correct
4 Correct 7 ms 9952 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 5 ms 9960 KB Output isn't correct
9 Halted 0 ms 0 KB -