oj.uz

Submission #940269

# Submission time Handle Problem Language Result Execution time Memory
940269 2024-03-07T07:20:12 Z GrandTiger1729 Passport (JOI23_passport) C++17
48 / 100
 2000 ms 63268 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10, INF = 1e9 + 10;
struct SegTree
{
    int l, r, mid;
    SegTree *lc, *rc;
    int val = INF;
    SegTree(int l_, int r_) : l(l_), r(r_)
    {
        mid = (l + r) / 2;
        if (l == r - 1)
        {
            return;
        }
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
    }
    ~SegTree()
    {
        if (l == r - 1)
        {
            return;
        }
        delete lc;
        delete rc;
    }
    void update(int i, int u)
    {
        if (l == r - 1)
        {
            val = u;
            return;
        }
        if (i < mid)
        {
            lc->update(i, u);
        }
        else
        {
            rc->update(i, u);
        }
        val = min(lc->val, rc->val);
    }
    int query(int ll, int rr)
    {
        if (ll <= l && rr >= r)
        {
            return val;
        }
        int ret = INF;
        if (ll < mid)
        {
            ret = min(ret, lc->query(ll, rr));
        }
        if (mid < rr)
        {
            ret = min(ret, rc->query(ll, rr));
        }
        return ret;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        l--;
        a[i] = make_pair(l, r);
    }
    vector<int> dpl(n, INF), dpr(n, INF);
    SegTree stl(0, n);
    stl.update(0, 0);
    dpl[0] = 0;
    for (int i = 1; i < n; i++)
    {
        dpl[i] = min(dpl[i], a[i].first > 0 ? 1 + stl.query(a[i].first, i) : 0);
        stl.update(i, dpl[i]);
    }
    SegTree str(0, n);
    str.update(n - 1, 0);
    dpr[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--)
    {
        dpr[i] = a[i].second < n ? 1 + str.query(i, a[i].second) : 0;
        str.update(i, dpr[i]);
    }
    vector<pair<int, int>> res(n);
    for (int i = 0; i < n; i++)
    {
        res[i] = make_pair(min(INF, min(dpl[i], 1 + stl.query(a[i].first, a[i].second)) + min(dpr[i], 1 + str.query(a[i].first, a[i].second))), i);
    }
    sort(res.begin(), res.end());
    vector<int> ans(n, INF);
    SegTree st(0, n);
    for (int tt = 0; tt < n; tt++)
    {
            for (auto [d, i] : res)
            {
                ans[i] = min(ans[i], min(d, 1 + st.query(a[i].first, a[i].second)));
                st.update(i, ans[i]);
            }
    }
    int q;
    cin >> q;
    while (q--)
    {
            int i;
            cin >> i;
            i--;
            cout << (ans[i] == INF ? -1 : ans[i] + 1) << '\n';
    }
    return 0;
    }

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Execution timed out 2090 ms 63268 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 548 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 8 ms 548 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 6 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 548 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 8 ms 548 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 6 ms 348 KB Output is correct
16 Correct 1048 ms 1184 KB Output is correct
17 Correct 823 ms 1364 KB Output is correct
18 Correct 1002 ms 1228 KB Output is correct
19 Correct 950 ms 1204 KB Output is correct
20 Correct 639 ms 1224 KB Output is correct
21 Correct 782 ms 1232 KB Output is correct
22 Correct 322 ms 1248 KB Output is correct
23 Correct 728 ms 1228 KB Output is correct
24 Correct 969 ms 1360 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 548 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 8 ms 548 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 6 ms 348 KB Output is correct
16 Correct 1048 ms 1184 KB Output is correct
17 Correct 823 ms 1364 KB Output is correct
18 Correct 1002 ms 1228 KB Output is correct
19 Correct 950 ms 1204 KB Output is correct
20 Correct 639 ms 1224 KB Output is correct
21 Correct 782 ms 1232 KB Output is correct
22 Correct 322 ms 1248 KB Output is correct
23 Correct 728 ms 1228 KB Output is correct
24 Correct 969 ms 1360 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1133 ms 1216 KB Output is correct
28 Correct 847 ms 1240 KB Output is correct
29 Correct 638 ms 1240 KB Output is correct
30 Correct 741 ms 1244 KB Output is correct
31 Correct 738 ms 1116 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Execution timed out 2090 ms 63268 KB Time limit exceeded
5 Halted 0 ms 0 KB -