QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #296974 | #6627. Line Town | A_programmer | 0 | 4ms | 21004kb | C++20 | 5.9kb | 2024-01-03 20:40:52 | 2024-01-03 20:40:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
stack<pii> st;
vector<int> v1, v2;
ll dp[maxn][2];
int a[maxn], id[maxn];
bool cmp(int x, int y) { return abs(a[x]) > abs(a[y]); }
struct BIT
{
int c[maxn];
void add(int x, int d) { for (; x < maxn; x += (x & -x)) c[x] += d; }
int sum(int x) { if (!x) return 0; int ans = 0; for (; x; x -= (x & -x)) ans += c[x]; return ans; }
}bitn, bita, bitp;
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], id[i] = i, bita.add(i, 1);
sort(id + 1, id + n + 1, cmp);
int l = 1, c = 0;
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
while (l <= n)
{
c++;
int r = l;
while (r < n && abs(a[id[r + 1]]) == abs(a[id[l]])) r++;
v1.clear(); v2.clear();
while (st.size()) st.pop();
if (!a[id[l]])
{
dp[c][0] = dp[c - 1][0];
dp[c][1] = dp[c - 1][1];
break;
}
else
{
for (int i = l; i <= r; i++)
{
bita.add(id[i], -1);
if ((a[id[i]] > 0) ^ (id[i] & 1)) v1.emplace_back(id[i]);
else v2.emplace_back(id[i]);
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int sz1 = v1.size(), sz2 = v2.size();
if (abs(sz1 - sz2) > 2)
{
l = r + 1;
continue;
}
bool lop = 0, rop = (n - l + 1) & 1;
int pos1 = sz1 - 1, pos2 = sz2 - 1;
ll res = 0;
for (int i = 1; i <= r - l + 1; i++)
{
if (rop ^ (i & 1))
{
if (pos1 < 0) break;
st.push(make_pair(v1[pos1], 1));
res += bitn.sum(v1[pos1]);
res += bita.sum(n) - bita.sum(v1[pos1]);
bitn.add(v1[pos1--], 1);
}
else
{
if (pos2 < 0) break;
st.push(make_pair(v2[pos2], 0));
res += bitn.sum(v2[pos2]);
res += bita.sum(n) - bita.sum(v2[pos2]);
bitn.add(v2[pos2--], 1);
}
}
int nx1 = pos1, nx2 = pos2; pos1 = pos2 = -1;
if (nx1 == -1 && nx2 == -1) dp[c][0] = min(dp[c][0], dp[c - 1][0] + res);
for (int i = 1; i <= r - l + 1; i++)
{
if (st.size() > (r - l + 1 - i))
{
pii tmp = st.top(); st.pop();
if (tmp.second) nx1++;
else nx2++;
bitn.add(tmp.first, -1);
res -= bitn.sum(tmp.first);
res -= bita.sum(n) - bita.sum(tmp.first);
res -= bitp.sum(n) - bitp.sum(tmp.first);
}
if (lop ^ (i & 1))
{
if (abs(nx1 - nx2) > 1 || ((nx1 <= nx2) ^ lop) || nx1 + nx2 + 2 != i) continue;
if (pos2 < nx2)
{
pos2++;
res += bita.sum(v2[pos2]);
res += bitn.sum(v2[pos2]);
res += bitp.sum(n) - bitp.sum(v2[pos2]);
bitp.add(v2[pos2], 1);
}
if (pos1 < nx1)
{
pos1++;
res += bita.sum(v1[pos1]);
res += bitn.sum(v1[pos1]);
res += bitp.sum(n) - bitp.sum(v1[pos1]);
bitp.add(v1[pos1], 1);
}
dp[c][1] = min(dp[c][1], dp[c - 1][0] + res);
}
else
{
if (abs(nx1 - nx2) > 1 || ((nx1 <= nx2) ^ lop) || nx1 + nx2 + 2 != i) continue;
if (pos1 < nx1)
{
pos1++;
res += bita.sum(v1[pos1]);
res += bitn.sum(v1[pos1]);
res += bitp.sum(n) - bitp.sum(v1[pos1]);
bitp.add(v1[pos1], 1);
}
if (pos2 < nx2)
{
pos2++;
res += bita.sum(v2[pos2]);
res += bitn.sum(v2[pos2]);
res += bitp.sum(n) - bitp.sum(v2[pos2]);
bitp.add(v2[pos2], 1);
}
dp[c][0] = min(dp[c][0], dp[c - 1][0] + res);
}
}
for (int i = 0; i < pos1; i++) bitp.add(v1[i], -1);
for (int i = 0; i < pos2; i++) bitp.add(v2[i], -1);
lop ^= 1, rop ^= 1;
while (st.size()) st.pop();
pos1 = sz1 - 1, pos2 = sz2 - 1, res = 0;
for (int i = 1; i <= r - l + 1; i++)
{
if (rop ^ (i & 1))
{
if (pos1 < 0) break;
st.push(make_pair(v1[pos1], 1));
res += bitn.sum(v1[pos1]);
res += bita.sum(n) - bita.sum(v1[pos1]);
bitn.add(v1[pos1--], 1);
}
else
{
if (pos2 < 0) break;
st.push(make_pair(v2[pos2], 0));
res += bitn.sum(v2[pos2]);
res += bita.sum(n) - bita.sum(v2[pos2]);
bitn.add(v2[pos2--], 1);
}
}
nx1 = pos1, nx2 = pos2, pos1 = pos2 = -1;
if (nx1 == -1 && nx2 == -1) dp[c][1] = min(dp[c][1], dp[c - 1][1] + res);
for (int i = 1; i <= r - l + 1; i++)
{
if (st.size() > (r - l + 1 - i))
{
pii tmp = st.top(); st.pop();
if (tmp.second) nx1++;
else nx2++;
bitn.add(tmp.first, -1);
res -= bitn.sum(tmp.first);
res -= bita.sum(n) - bita.sum(tmp.first);
}
if (lop ^ (i & 1))
{
if (abs(nx1 - nx2) > 1 || ((nx1 <= nx2) ^ lop) || nx1 + nx2 + 2 != i) continue;
if (pos2 < nx2)
{
pos2++;
res += bita.sum(v2[pos2]);
res += bitn.sum(v2[pos2]);
res += bitp.sum(n) - bitp.sum(v2[pos2]);
bitp.add(v2[pos2], 1);
}
if (pos1 < nx1)
{
pos1++;
res += bita.sum(v1[pos1]);
res += bitn.sum(v1[pos1]);
res += bitp.sum(n) - bitp.sum(v1[pos1]);
bitp.add(v1[pos1], 1);
}
dp[c][1] = min(dp[c][1], dp[c - 1][1] + res);
}
else
{
if (abs(nx1 - nx2) > 1 || ((nx1 <= nx2) ^ lop) || nx1 + nx2 + 2 != i) continue;
if (pos1 < nx1)
{
pos1++;
res += bita.sum(v1[pos1]);
res += bitn.sum(v1[pos1]);
res += bitp.sum(n) - bitp.sum(v1[pos1]);
bitp.add(v1[pos1], 1);
}
if (pos2 < nx2)
{
pos2++;
res += bita.sum(v2[pos2]);
res += bitn.sum(v2[pos2]);
res += bitp.sum(n) - bitp.sum(v2[pos2]);
bitp.add(v2[pos2], 1);
}
dp[c][0] = min(dp[c][0], dp[c - 1][1] + res);
}
}
for (int i = 0; i < pos1; i++) bitp.add(v1[i], -1);
for (int i = 0; i < pos2; i++) bitp.add(v2[i], -1);
}
l = r + 1;
}
ll ans = min(dp[c][0], dp[c][1]);
cout << (ans > 1e18 ? -1 : ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 0ms
memory: 17544kb
input:
10 1 1 1 1 1 -1 -1 -1 1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 20956kb
input:
10 1 1 1 1 1 1 -1 1 1 -1
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 3ms
memory: 18092kb
input:
1 -1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 4ms
memory: 19108kb
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: 0
Accepted
time: 0ms
memory: 17880kb
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
Wrong Answer
time: 4ms
memory: 20452kb
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:
18790
result:
wrong answer 1st numbers differ - expected: '18090', found: '18790'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Wrong Answer
Test #60:
score: 4
Accepted
time: 2ms
memory: 21004kb
input:
10 3 10 5 -9 7 2 -6 1 8 0
output:
-1
result:
ok 1 number(s): "-1"
Test #61:
score: -4
Wrong Answer
time: 0ms
memory: 20236kb
input:
10 -9 0 -1 7 5 10 6 3 2 -8
output:
16
result:
wrong answer 1st numbers differ - expected: '13', found: '16'
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%