QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487012 | #8258. Gift Exchange | bashkort | 9 | 0ms | 3892kb | C++20 | 4.1kb | 2024-07-22 15:10:19 | 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%