QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#117259 | #6627. Line Town | pandapythoner# | 6 | 27ms | 15924kb | C++20 | 1.8kb | 2023-06-30 19:28:53 | 2024-05-31 18:43:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(234);
const ll inf = 1e17;
int n;
vector<ll> h;
ll solve_abs_1() {
vector<int> a(n + 2);
a[0] = 0;
a[n + 1] = 1;
for (int i = 0; i < n; i += 1) {
if (h[i] < 0) {
a[i + 1] = 0;
} else {
a[i + 1] = 1;
}
}
vector<int> d(n + 1);
for (int i = 0; i <= n; i += 1) {
d[i] = (a[i] ^ a[i + 1]);
}
vector<int> stck;
vector<ll> bebra(n + 1, inf);
ll sm = 0;
for (int i = 0; i <= n; i += 1) {
if (d[i]) {
if (!stck.empty() && stck.back() % 2 == i % 2) {
sm += (i - stck.back()) / 2;
stck.pop_back();
} else {
stck.push_back(i);
}
if (stck.size() == 1) {
bebra[i] = sm;
}
}
}
ll rs = inf;
stck.clear();
sm = 0;
for (int i = n; i >= 0; i -= 1) {
if (stck.empty()) {
rs = min(rs, sm + bebra[i]);
}
if (d[i]) {
if (!stck.empty() && stck.back() % 2 == i % 2) {
sm += (stck.back() - i) / 2;
stck.pop_back();
} else {
stck.push_back(i);
}
}
}
if (rs > inf / 4) {
return -1;
}
return rs;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
h.resize(n);
for (int i = 0; i < n; i += 1) {
cin >> h[i];
}
cout << solve_abs_1() << "\n";
return 0;
}
/*
4
1 -1 1 -1
4
1 1 -1 -1
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 0ms
memory: 3644kb
input:
10 1 1 1 1 1 -1 -1 -1 1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #2:
score: 3
Accepted
time: 0ms
memory: 3528kb
input:
10 1 1 1 1 1 1 -1 1 1 -1
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 3
Accepted
time: 1ms
memory: 3844kb
input:
1 -1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 3
Accepted
time: 1ms
memory: 3932kb
input:
2000 1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 ...
output:
15146
result:
ok 1 number(s): "15146"
Test #5:
score: 3
Accepted
time: 0ms
memory: 3936kb
input:
2000 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 -1 -1 ...
output:
24933
result:
ok 1 number(s): "24933"
Test #6:
score: 3
Accepted
time: 1ms
memory: 3936kb
input:
2000 1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 -...
output:
18090
result:
ok 1 number(s): "18090"
Test #7:
score: 3
Accepted
time: 1ms
memory: 3632kb
input:
2000 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 1...
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 3
Accepted
time: 0ms
memory: 3700kb
input:
2000 -1 1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 ...
output:
9973
result:
ok 1 number(s): "9973"
Test #9:
score: 3
Accepted
time: 1ms
memory: 3700kb
input:
2000 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...
output:
499500
result:
ok 1 number(s): "499500"
Test #10:
score: 3
Accepted
time: 1ms
memory: 3644kb
input:
2000 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...
output:
499500
result:
ok 1 number(s): "499500"
Test #11:
score: 3
Accepted
time: 0ms
memory: 3636kb
input:
1999 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...
output:
499500
result:
ok 1 number(s): "499500"
Test #12:
score: 3
Accepted
time: 1ms
memory: 3640kb
input:
1997 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...
output:
498501
result:
ok 1 number(s): "498501"
Test #13:
score: 3
Accepted
time: 1ms
memory: 3564kb
input:
2000 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...
output:
-1
result:
ok 1 number(s): "-1"
Subtask #2:
score: 3
Accepted
Dependency #1:
100%
Accepted
Test #14:
score: 3
Accepted
time: 0ms
memory: 3808kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 3
Accepted
time: 27ms
memory: 14956kb
input:
500000 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 -1 1 ...
output:
29737766
result:
ok 1 number(s): "29737766"
Test #16:
score: 3
Accepted
time: 25ms
memory: 15032kb
input:
500000 1 -1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1...
output:
66957355
result:
ok 1 number(s): "66957355"
Test #17:
score: 3
Accepted
time: 24ms
memory: 14892kb
input:
500000 1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1...
output:
50480873
result:
ok 1 number(s): "50480873"
Test #18:
score: 3
Accepted
time: 24ms
memory: 14952kb
input:
500000 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 -1 -1 -1...
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: 3
Accepted
time: 24ms
memory: 15000kb
input:
500000 1 1 1 1 -1 -1 -1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 -1 1 1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1...
output:
90473670
result:
ok 1 number(s): "90473670"
Test #20:
score: 3
Accepted
time: 19ms
memory: 15924kb
input:
500000 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...
output:
31249875000
result:
ok 1 number(s): "31249875000"
Test #21:
score: 3
Accepted
time: 11ms
memory: 15876kb
input:
500000 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...
output:
31249875000
result:
ok 1 number(s): "31249875000"
Test #22:
score: 3
Accepted
time: 18ms
memory: 15920kb
input:
499999 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...
output:
31249875000
result:
ok 1 number(s): "31249875000"
Test #23:
score: 3
Accepted
time: 13ms
memory: 15920kb
input:
499997 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...
output:
31249375003
result:
ok 1 number(s): "31249375003"
Test #24:
score: 3
Accepted
time: 19ms
memory: 15924kb
input:
500000 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...
output:
-1
result:
ok 1 number(s): "-1"
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #25:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
10 0 1 0 0 1 1 -1 0 1 -1
output:
3
result:
wrong answer 1st numbers differ - expected: '9', found: '3'
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #44:
score: 0
Wrong Answer
time: 19ms
memory: 15036kb
input:
500000 1 1 -1 0 0 -1 1 -1 0 0 1 1 -1 -1 -1 1 -1 1 0 0 -1 1 1 0 0 0 0 0 1 0 -1 0 -1 1 1 0 0 -1 1 0 0 0 0 0 -1 0 0 -1 1 1 0 0 1 0 0 1 -1 0 1 0 0 0 0 -1 1 0 1 0 -1 0 -1 1 1 0 -1 0 0 0 0 0 0 1 -1 1 -1 1 0 1 -1 0 1 -1 0 -1 -1 1 1 0 1 0 -1 0 0 0 -1 0 -1 0 0 1 -1 1 0 0 1 0 1 0 1 0 0 -1 0 1 1 -1 -1 0 0 -1 -...
output:
-1
result:
wrong answer 1st numbers differ - expected: '15602272809', found: '-1'
Subtask #5:
score: 0
Wrong Answer
Test #60:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
10 3 10 5 -9 7 2 -6 1 8 0
output:
3
result:
wrong answer 1st numbers differ - expected: '-1', found: '3'
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%