oj.uz

답안 #800557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800557 2023-08-01T16:09:25 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 500 ms 56096 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);
                        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 = 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 7 ms 9900 KB Output is correct
2 Correct 6 ms 9960 KB Output is correct
3 Correct 5 ms 9964 KB Output is correct
4 Correct 8 ms 9864 KB Output is correct
5 Correct 5 ms 9964 KB Output is correct
6 Correct 8 ms 9892 KB Output is correct
7 Correct 5 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

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

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 48556 KB Output is correct
2 Correct 185 ms 48432 KB Output is correct
3 Correct 231 ms 49676 KB Output is correct
4 Correct 161 ms 48048 KB Output is correct
5 Incorrect 294 ms 56096 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 13.0

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