oj.uz

Submission #800417

# Submission time Handle Problem Language Result Execution time Memory
800417 2023-08-01T14:31:36 Z caganyanmaz Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 630 ms 70088 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 = 2e5;
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 s, t;
                cin >> s >> t;
                s--, t--;
                if (st[MXLOG-1][s+n][0] > t || st[MXLOG-1][s+n][1] < t)
                {
                        cout << "-1\n";
                        continue;
                }
                int dist = 0, l = s, r = s;
                for (int i = MXLOG-1; i >= 0; i--)
                {
                        auto [nl, nr] = get(i, l, r+1);
                        if (nl > t || nr < t)
                        {
                                l = nl, r = nr;
                                dist |= 1<<i;
                        }
                }
                cout << (dist+1) << "\n";
        }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10068 KB Output is correct
2 Correct 5 ms 9964 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 6 ms 10068 KB Output is correct
5 Correct 7 ms 9960 KB Output is correct
6 Correct 7 ms 10088 KB Output is correct
7 Correct 6 ms 9960 KB Output is correct
8 Incorrect 5 ms 10048 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 10068 KB Output is correct
2 Correct 5 ms 9964 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 6 ms 10068 KB Output is correct
5 Correct 7 ms 9960 KB Output is correct
6 Correct 7 ms 10088 KB Output is correct
7 Correct 6 ms 9960 KB Output is correct
8 Incorrect 5 ms 10048 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 62632 KB Output is correct
2 Correct 196 ms 62456 KB Output is correct
3 Correct 240 ms 63724 KB Output is correct
4 Correct 229 ms 62052 KB Output is correct
5 Incorrect 289 ms 70088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 13.0

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