QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487012#8258. Gift Exchangebashkort9 0ms3892kbC++204.1kb2024-07-22 15:10:192024-07-22 15:10:19

Judging History

你现在查看的是最新测评结果

  • [2024-07-22 15:10:19]
  • 评测
  • 测评结果:9
  • 用时:0ms
  • 内存:3892kb
  • [2024-07-22 15:10:19]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int inf = 1e9 + 7;

struct SegmentTree {
    vector<int> t;
    int sz;

    void init(int m) {
        sz = 1 << __lg(m) + !!(m & (m - 1));
        t.assign(2 * sz, inf);
    }

    void rangeApply(int l, int r, int x) {
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                t[l] = min(t[l], x);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                t[r] = min(t[r], x);
            }
        }
    }

    int rangeMin(int l, int r) {
        int ans = inf;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                ans = min(ans, t[l++]);
            }
            if (r & 1) {
                ans = min(ans, t[--r]);
            }
        }
        return ans;
    }

    int query(int x) {
        int ans = inf;
        for (ans = t[x += sz]; x >>= 1; ) {
            ans = min(ans, t[x]);
        }
        return ans;
    }

    void modify(int x, int f) {
        x += sz;
        t[x] = min(t[x], f);
        while (x >>= 1) {
            t[x] = min(t[x << 1], t[x << 1 | 1]);
        }
    }
};

template<typename T>
struct Fenwick {
    int n;
    vector<T> a;

    Fenwick() = default;

    explicit Fenwick(int n) : n(n), a(n + 1) {}

    void modify(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i] += v;
        }
    }

    void modify(int l, int r, T v) {
        if (l >= r) return;
        modify(l, v), modify(r, -v);
    }

    T sum(int x) {
        T ans = 0;
        for (int i = x + 1; i > 0; i -= i & -i) {
            ans += a[i];
        }
        return ans;
    }

    T rangeSum(int l, int r) { //[l, r)
        if (l >= r) return 0;
        return sum(r - 1) - sum(l - 1);
    }

    int kth(T k) {
        int x = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (x + i <= n && k > a[x + i]) {
                x += i;
                k -= a[x];
            }
        }
        return x;
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        --b[i];
    }

    vector<int> L(n, -1), R(n, n);
    for (int t = 0; t < 2; ++t) {
        SegmentTree tree, range;
        tree.init(100), range.init(100);
        vector<int> res(n, n);
        for (int i = n - 1; i >= 0; --i) {
            res[i] = min({res[i], tree.query(a[i]), tree.query(b[i]), range.rangeMin(b[i], a[i])});
            tree.rangeApply(b[i], a[i] + 1, i);
            range.modify(a[i], i);
            range.modify(b[i], i);
        }
        if (t == 0) {
            R = res;
        } else {
            L = res;
            reverse(L.begin(), L.end());
            for (int &x : L) {
                x = n - x - 1;
            }
        }
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
    }

    vector<vector<int>> updates(n + 1);
    for (int i = 0; i < n; ++i) {
        updates[R[i]].push_back(i);
    }

    int q;
    cin >> q;
    vector<vector<pair<int, int>>> queries(n);
    vector<int> answers(q);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[r - 1].push_back({l - 1, i});
    }

    Fenwick<int> fn(n);
    for (int i = 0; i < n; ++i) {
        if (L[i] >= 0) {
            fn.modify(L[i], 1);
        }
        for (int j : updates[i]) {
            if (L[j] >= 0) {
                fn.modify(L[j], -1);
            }
            fn.modify(j, 1);
        }
        for (auto [l, k] : queries[i]) {
            if (fn.rangeSum(l, i + 1) == i - l + 1) {
                answers[k] = true;
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << (answers[i] ? "Yes\n" : "No\n");
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 0ms
memory: 3532kb

input:

10
13 14 16 18 17 19 20 8 6 4
7 12 15 2 11 10 9 3 5 1
10
2 3
1 6
1 7
5 8
1 10
2 6
5 10
3 6
3 7
4 7

output:

No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 8, no count is 2

Test #2:

score: 4
Accepted
time: 0ms
memory: 3884kb

input:

10
12 19 15 20 14 9 4 13 17 16
11 18 7 5 10 8 3 1 2 6
10
6 10
2 6
6 7
3 8
1 8
7 8
6 8
4 5
1 7
4 5

output:

Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes

result:

ok 10 token(s): yes count is 8, no count is 2

Test #3:

score: 4
Accepted
time: 0ms
memory: 3640kb

input:

10
15 8 12 19 6 10 16 18 20 17
13 3 5 14 1 4 9 7 2 11
10
1 3
2 6
5 7
1 4
2 7
1 2
2 5
1 3
2 6
4 5

output:

No
No
Yes
Yes
Yes
No
No
No
No
No

result:

ok 10 token(s): yes count is 3, no count is 7

Test #4:

score: 4
Accepted
time: 0ms
memory: 3644kb

input:

10
15 9 13 20 17 19 8 3 10 16
11 7 5 18 2 12 6 1 4 14
10
1 2
4 7
6 7
7 10
3 6
6 10
6 10
6 7
1 3
1 2

output:

No
Yes
No
No
Yes
No
No
No
Yes
No

result:

ok 10 token(s): yes count is 3, no count is 7

Test #5:

score: 4
Accepted
time: 0ms
memory: 3808kb

input:

7
14 7 5 8 12 10 13
4 6 3 2 11 9 1
10
4 5
3 7
1 5
1 3
5 6
3 7
3 7
4 7
5 7
4 5

output:

No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No

result:

ok 10 token(s): yes count is 7, no count is 3

Test #6:

score: 4
Accepted
time: 0ms
memory: 3892kb

input:

10
14 2 10 19 4 20 16 15 8 17
13 1 9 7 3 18 12 11 6 5
10
8 9
1 9
7 10
2 6
9 10
5 8
1 2
1 9
2 3
6 8

output:

No
No
Yes
No
Yes
No
No
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #7:

score: 4
Accepted
time: 0ms
memory: 3660kb

input:

10
9 12 19 5 13 17 7 15 10 20
8 1 18 2 4 16 6 14 3 11
10
1 8
3 6
2 3
2 3
7 9
5 9
3 8
7 10
5 9
4 8

output:

No
No
No
No
No
No
No
Yes
No
No

result:

ok 10 token(s): yes count is 1, no count is 9

Test #8:

score: 4
Accepted
time: 0ms
memory: 3848kb

input:

10
20 11 4 9 19 15 8 13 14 17
3 10 1 6 18 12 7 2 5 16
10
4 5
4 8
3 10
4 10
4 6
2 9
3 10
4 8
3 5
7 10

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Test #9:

score: 4
Accepted
time: 0ms
memory: 3812kb

input:

10
15 17 20 12 11 2 18 8 14 16
13 10 19 3 9 1 6 7 4 5
10
2 10
1 9
2 9
2 10
2 9
2 9
2 9
1 9
1 9
2 9

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Test #10:

score: 4
Accepted
time: 0ms
memory: 3848kb

input:

10
14 20 11 10 6 15 18 12 4 17
7 19 9 5 2 3 13 8 1 16
10
1 10
1 9
2 10
1 8
2 9
3 10
1 7
2 8
3 9
4 10

output:

No
No
No
No
No
Yes
No
No
Yes
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #11:

score: 4
Accepted
time: 0ms
memory: 3580kb

input:

10
4 18 20 12 2 10 6 16 8 14
3 17 19 11 1 9 5 15 7 13
10
3 6
6 10
2 10
1 10
1 4
3 9
6 9
6 10
3 10
4 5

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Test #12:

score: 4
Accepted
time: 0ms
memory: 3808kb

input:

10
14 12 18 17 20 15 19 16 13 11
6 5 7 9 4 10 2 3 1 8
10
3 5
3 9
3 7
3 4
3 5
9 10
1 8
3 10
1 10
4 6

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #13:

score: 4
Accepted
time: 0ms
memory: 3884kb

input:

10
17 19 8 20 7 15 10 3 18 6
14 16 1 13 4 12 9 2 11 5
10
3 10
4 9
3 5
8 9
6 9
3 8
5 7
4 5
3 4
2 5

output:

No
No
No
No
No
No
No
No
No
Yes

result:

ok 10 token(s): yes count is 1, no count is 9

Test #14:

score: 4
Accepted
time: 0ms
memory: 3808kb

input:

2
4 3
2 1
1
1 2

output:

Yes

result:

ok YES

Test #15:

score: 4
Accepted
time: 0ms
memory: 3584kb

input:

2
2 4
1 3
1
1 2

output:

No

result:

ok NO

Test #16:

score: 4
Accepted
time: 0ms
memory: 3584kb

input:

3
4 5 6
1 2 3
1
1 3

output:

Yes

result:

ok YES

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 5
Accepted
time: 0ms
memory: 3684kb

input:

15
29 20 30 4 9 2 24 19 17 25 18 28 21 6 23
26 10 27 3 8 1 14 15 11 16 12 22 7 5 13
10
8 14
5 15
9 11
5 10
8 11
2 13
4 9
8 13
6 14
9 12

output:

No
No
Yes
No
Yes
No
No
Yes
No
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #18:

score: 5
Accepted
time: 0ms
memory: 3880kb

input:

18
28 31 8 25 36 11 10 32 33 34 26 27 9 20 18 19 35 24
5 4 2 23 17 6 3 22 21 29 1 16 7 15 12 13 30 14
10
8 10
9 17
13 17
13 16
5 11
10 15
5 16
1 15
6 16
6 16

output:

Yes
Yes
No
No
Yes
No
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 7, no count is 3

Test #19:

score: 5
Accepted
time: 0ms
memory: 3876kb

input:

18
30 21 27 20 34 10 25 18 19 22 15 9 28 29 35 32 26 36
4 11 1 3 17 2 24 13 7 5 14 6 23 12 33 31 16 8
10
8 16
6 8
7 8
5 15
4 18
7 8
13 15
3 7
6 8
6 13

output:

No
No
No
Yes
Yes
No
No
Yes
No
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #20:

score: 5
Accepted
time: 0ms
memory: 3884kb

input:

18
20 30 27 36 21 12 31 19 24 35 23 32 18 25 26 34 14 33
1 16 6 17 11 10 15 5 9 7 3 4 2 22 8 29 13 28
10
6 16
17 18
3 6
15 17
17 18
13 14
13 14
15 16
7 13
8 14

output:

Yes
No
Yes
No
No
No
No
No
Yes
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #21:

score: 5
Accepted
time: 0ms
memory: 3812kb

input:

16
16 25 14 29 18 30 4 17 7 9 8 19 31 22 21 32
5 24 13 28 12 27 3 15 6 2 1 11 26 10 20 23
10
4 13
2 10
12 16
1 2
10 11
4 7
3 8
1 10
6 10
10 11

output:

Yes
No
Yes
No
Yes
No
No
No
No
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #22:

score: 5
Accepted
time: 0ms
memory: 3812kb

input:

18
4 26 11 5 27 13 19 24 35 29 31 34 32 18 16 7 36 14
1 9 8 3 25 12 10 22 33 28 30 23 21 17 15 6 20 2
10
9 16
2 14
5 15
16 18
6 17
4 15
6 13
4 18
2 3
9 18

output:

No
No
Yes
No
No
No
Yes
Yes
Yes
No

result:

ok 10 token(s): yes count is 4, no count is 6

Test #23:

score: 5
Accepted
time: 0ms
memory: 3648kb

input:

18
11 24 18 20 3 33 34 27 30 22 36 28 19 9 15 10 5 29
6 23 17 13 2 32 31 12 25 1 35 21 16 8 14 7 4 26
10
5 8
2 6
9 11
12 16
5 8
14 18
13 17
12 14
9 18
13 18

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Test #24:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

18
28 25 17 26 18 8 35 3 36 34 12 13 21 32 29 20 30 31
19 24 16 23 15 7 10 1 22 33 11 9 4 5 27 14 6 2
10
6 8
15 16
2 5
10 11
10 15
1 18
2 8
2 3
5 18
2 3

output:

No
No
Yes
No
No
Yes
No
No
Yes
No

result:

ok 10 token(s): yes count is 3, no count is 7

Test #25:

score: 5
Accepted
time: 0ms
memory: 3644kb

input:

18
20 30 36 22 23 24 35 18 11 14 27 8 9 15 28 34 32 33
3 17 6 21 4 19 13 2 1 12 26 5 7 10 25 31 29 16
10
2 17
2 17
1 17
1 18
1 17
1 18
2 18
1 17
2 17
1 18

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #26:

score: 5
Accepted
time: 0ms
memory: 3536kb

input:

18
21 23 29 27 36 4 32 18 34 35 11 33 26 7 14 31 5 15
13 22 9 19 17 3 24 16 10 28 8 30 25 6 12 20 1 2
10
1 18
1 17
2 18
1 16
2 17
3 18
1 15
2 16
3 17
4 18

output:

Yes
No
Yes
No
No
Yes
No
No
No
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #27:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

18
8 26 36 16 22 18 10 32 30 14 12 34 28 4 24 20 2 6
7 25 35 15 21 17 9 31 29 13 11 33 27 3 23 19 1 5
10
9 11
15 18
2 14
8 16
5 8
2 16
4 6
7 17
1 8
8 18

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Test #28:

score: 5
Accepted
time: 0ms
memory: 3620kb

input:

18
22 34 20 30 19 35 25 31 32 28 27 33 26 21 29 23 36 24
5 6 11 18 16 13 8 9 14 2 1 3 15 7 12 4 10 17
10
13 15
1 8
1 2
8 11
1 16
5 18
8 18
3 14
1 14
2 13

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #29:

score: 5
Accepted
time: 0ms
memory: 3812kb

input:

18
12 17 30 19 18 32 14 22 36 35 27 29 25 21 9 28 16 20
5 1 26 10 3 31 13 6 34 33 11 2 23 4 8 24 15 7
10
9 17
5 13
10 17
6 11
2 14
13 16
4 17
8 10
6 16
2 15

output:

Yes
No
No
No
No
Yes
No
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Subtask #3:

score: 0
Runtime Error

Test #30:

score: 0
Runtime Error

input:

100000
200000 87337 190412 58171 10676 178924 155670 153538 106523 166320 196463 174807 19706 66971 196345 114283 119288 59218 155349 194059 154822 98022 199346 153510 145408 187388 174214 150932 65211 35112 20551 176504 139581 41024 52730 150416 18789 190510 108780 47812 169962 158959 135239 191992...

output:


result:


Subtask #4:

score: 0
Runtime Error

Test #39:

score: 0
Runtime Error

input:

74998
147369 94378 68913 123990 65257 88482 116281 130255 78568 141536 99818 113372 26849 44703 95080 48018 147366 120676 91071 19208 101933 124465 78741 140833 90216 52837 145872 105601 142557 113425 86814 84542 101123 108992 78297 100014 104368 69638 40964 118227 76398 117479 115743 72849 102952 1...

output:


result:


Subtask #5:

score: 0
Runtime Error

Test #52:

score: 0
Runtime Error

input:

71726
4 5 7 10 11 17 20 24 26 27 28 29 31 35 36 38 40 42 44 46 48 50 51 52 55 56 57 59 61 62 66 68 69 70 72 73 75 78 79 83 85 86 91 93 96 97 98 100 105 107 108 109 110 111 112 113 116 117 120 124 125 126 127 129 132 133 135 139 144 145 146 148 149 152 153 154 156 157 159 161 163 165 167 173 174 178 ...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%