QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#34302 | #4191. Hectic Harbour II | sinbad# | AC ✓ | 44ms | 10340kb | C++17 | 4.4kb | 2022-06-06 21:02:33 | 2022-06-06 21:02:34 |
Judging History
answer
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
// mt19937 mrand(random_device{}());
// int rnd(int x) { return mrand() % x; }
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
int lg2(int64 x) { return sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
int main() {
int n, L, R, x;
cin >> n >> L >> R;
vector<int> a, b;
for (int i = 0; i < L; ++i) {
cin >> x;
a.push_back(x);
}
for (int i = 0; i < R; ++i) {
cin >> x;
b.push_back(x);
}
while (SZ(b)) {
a.push_back(b.back());
b.pop_back();
}
n = SZ(a);
vector<int> pos(n);
for (int i = 0; i < n; ++i) pos[a[i]] = i;
vector<int> pre(n), nxt(n);
for (int i = 0; i < n; ++i) {
pre[i] = i - 1;
nxt[i] = i + 1;
}
int ret = 0;
for (int i = 1; i < n; ++i) {
int x = pos[i];
int ll = pre[x], rr = nxt[x];
if (ll >= 0 && a[ll] == 0) ++ret;
if (rr < n && a[rr] == 0) ++ret;
if (ll >= 0) nxt[ll] = rr;
if (rr < n) pre[rr] = ll;
}
cout << ret << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3636kb
input:
4 3 2 2 0 3 1 4
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
6 4 3 2 4 0 1 6 3 5
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
11 2 10 3 9 11 5 6 0 1 7 4 8 10 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
3 2 2 3 2 0 1
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
7 4 4 0 6 3 1 5 7 2 4
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
15 8 8 4 15 9 5 8 0 2 13 14 7 6 11 1 10 12 3
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
3 2 2 0 1 2 3
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
101 100 2 50 7 10 91 89 80 62 41 58 96 46 63 1 21 92 78 75 16 23 53 68 32 8 0 18 30 69 15 38 76 28 19 73 4 77 6 84 100 97 64 88 101 67 14 17 43 40 60 85 44 35 48 31 56 61 82 70 90 45 94 52 93 22 71 26 2 86 9 55 95 83 39 36 87 29 81 72 79 65 20 37 51 47 12 5 74 99 11 3 42 66 27 33 13 54 49 24 59 98 2...
output:
15
result:
ok single line: '15'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
101 2 100 68 69 7 67 50 37 49 24 56 13 46 53 73 8 80 14 2 21 23 55 84 52 92 27 87 93 76 91 42 75 25 60 66 57 98 34 35 40 12 95 62 79 81 86 3 5 89 47 1 43 4 48 20 78 30 77 59 99 65 85 10 22 32 29 31 0 74 54 39 82 41 101 6 18 72 94 71 90 51 28 96 33 83 17 44 19 36 70 9 45 11 63 61 26 97 16 100 88 58 3...
output:
7
result:
ok single line: '7'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
399 200 200 313 372 375 49 286 369 155 170 188 114 42 289 73 249 70 393 172 207 133 295 327 60 271 72 161 103 92 309 221 85 169 1 333 100 367 259 147 365 389 89 253 38 184 332 0 47 145 300 270 63 41 319 284 107 135 326 329 187 180 383 76 12 213 93 262 26 358 244 395 177 104 98 7 191 118 74 122 398 3...
output:
13
result:
ok single line: '13'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
193 97 97 36 110 122 193 172 149 63 102 150 21 50 137 2 25 189 146 107 93 47 6 39 192 80 92 23 43 95 30 48 141 99 56 73 118 123 132 143 191 68 15 52 136 14 180 171 35 133 97 115 113 44 66 41 16 161 190 86 55 10 54 131 1 173 153 155 28 12 100 90 158 74 112 114 69 178 179 134 94 151 70 26 165 24 111 3...
output:
13
result:
ok single line: '13'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
1999 1000 1000 309 1788 1518 1587 1821 1236 904 1853 1622 599 66 1550 733 366 357 187 278 190 1972 1092 1973 286 1458 612 1909 829 399 488 815 1361 845 1656 1336 1991 565 1452 1760 1294 1002 247 397 644 273 814 402 37 1672 1774 55 1363 180 147 1636 995 482 1139 172 1948 431 580 920 848 271 1823 1026...
output:
15
result:
ok single line: '15'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
20000 10000 10001 9883 14711 10346 8769 11822 17563 10463 5503 1247 8993 1558 17028 655 77 14008 7304 7461 11588 10583 3879 16231 256 1933 18390 7954 6437 15146 3881 10657 5145 11319 1025 4049 7651 8825 11173 10589 16578 2872 3446 9417 6745 14923 13447 3643 2309 7597 3765 17914 6095 1470 11528 16815...
output:
9
result:
ok single line: '9'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
19030 30 19001 14251 10569 11881 16119 2880 5820 19024 4469 18054 8658 8098 14893 15866 2890 1899 14465 7069 18237 2798 18031 12426 500 14121 17003 10401 16613 12506 8705 15657 247 8132 7096 16560 3133 1666 12317 14885 2797 2446 16850 5195 6333 3141 1894 14293 8298 12558 15923 5710 13758 16956 12104...
output:
13
result:
ok single line: '13'
Test #15:
score: 0
Accepted
time: 6ms
memory: 3984kb
input:
40167 40000 168 7456 29753 30457 14826 28175 1908 39515 24571 1524 9896 2870 3025 38460 15788 286 14553 5875 14649 26432 28204 4710 39486 27216 12597 22453 39599 19407 21533 9909 36250 5204 35786 9614 32173 19491 38676 21815 29319 15124 26344 25894 4851 18646 13994 36641 30019 22334 38480 930 20185 ...
output:
23
result:
ok single line: '23'
Test #16:
score: 0
Accepted
time: 26ms
memory: 10316kb
input:
399999 200000 200000 98991 228035 191079 109294 45109 259958 228838 196508 123689 174720 958 155295 169919 250579 253195 14648 9714 168581 62550 191609 251316 382472 200019 28849 319628 143617 314937 350279 54701 320846 212855 29815 288369 4356 23726 130122 79710 223894 225102 214605 49355 246868 21...
output:
29
result:
ok single line: '29'
Test #17:
score: 0
Accepted
time: 44ms
memory: 10268kb
input:
399999 200000 200000 180608 307068 199608 266183 104614 135854 269310 140182 199654 206963 274625 385100 13963 207137 177700 300849 24017 2885 246826 100061 219924 84806 347728 211015 50631 98866 114542 24250 187908 3201 339843 99315 333365 308251 213371 20839 154882 251703 265366 45721 77964 15048 ...
output:
18
result:
ok single line: '18'
Test #18:
score: 0
Accepted
time: 30ms
memory: 10260kb
input:
399999 200000 200000 144226 308114 28104 348319 11330 110032 368774 71443 89011 234730 314461 382895 323950 360245 242387 331397 298029 223413 50503 9742 95332 219016 135117 150171 225489 229782 337065 12512 202132 77898 125512 374928 243070 331857 375969 368452 164342 342245 188351 68949 391879 130...
output:
25
result:
ok single line: '25'
Test #19:
score: 0
Accepted
time: 29ms
memory: 10340kb
input:
399999 200000 200000 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 ...
output:
3
result:
ok single line: '3'
Test #20:
score: 0
Accepted
time: 35ms
memory: 10328kb
input:
399999 200000 200000 399999 399998 399997 399996 399995 399994 399993 399992 399991 399990 399989 399988 399987 399986 399985 399984 399983 399982 399981 399980 399979 399978 399977 399976 399975 399974 399973 399972 399971 399970 399969 399968 399967 399966 399965 399964 399963 399962 399961 399960...
output:
399999
result:
ok single line: '399999'
Test #21:
score: 0
Accepted
time: 33ms
memory: 10268kb
input:
399999 200000 200000 399999 399998 399997 399996 399994 399992 399990 399988 399986 399984 399982 399980 399978 399976 399974 399972 399970 399968 399966 399964 399962 399960 399958 399956 399954 399952 399950 399948 399946 399944 399942 399940 399938 399936 399934 399932 399930 399928 399926 399924...
output:
399999
result:
ok single line: '399999'