QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #137680 | #6627. Line Town | penguinman# | 0 | 1ms | 3888kb | C++17 | 6.7kb | 2023-08-10 16:33:06 | 2024-07-04 01:29:41 |
Judging History
answer
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()
#define mtp std::make_tuple
constexpr ll inf = (1ll<<60);
template<typename T>
struct segment_tree{
ll N, valINF;
vector<T> node;
segment_tree(int n, T valINF_){
valINF = valINF_;
N = 1;
while(N <= n) N *= 2;
node.resize(2*N, valINF);
}
void update(ll idx, T val){
idx += N;
node[idx] = val;
idx /= 2;
while(idx){
node[idx] = compare(node[idx*2], node[idx*2+1]);
idx /= 2;
}
}
T calc(ll l, ll r){
T ret = valINF;
l += N;
r += N;
r--;
while(l < r){
if(l & 1){
ret = compare(ret, node[l]);
l++;
}
l /= 2;
if((r&1) == 0){
ret = compare(ret, node[r]);
r--;
}
r /= 2;
}
if(l == r) ret = compare(ret, node[l]);
return ret;
}
T compare(T l, T r){
return std::min(l, r);
}
};
template<typename T>
struct binary_indexed_tree{
ll N;
vector<T> node;
binary_indexed_tree(int n){
N = n;
node.resize(N+1);
}
void add(ll idx, ll val){
idx++;
for(; idx<=N; idx+=(idx&(-idx))){
node[idx] += val;
}
}
T sum(ll idx){
idx++;
T ret = 0;
for(; 0<idx; idx-=(idx&(-idx))){
ret += node[idx];
}
return ret;
}
};
int main(){
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
ll N; cin >> N;
vi A(N);
rep(i,0,N) cin >> A[i];
vector<pii> data(N);
rep(i,0,N) data[i] = mp(std::abs(A[i]), i);
sort(all(data));
reverse(all(data));
string S = "";
vi idx;
for(auto &el: data){
if(el.second%2) el.first = -A[el.second];
else el.first = A[el.second];
if(el.first == 0) S += '2';
else if(el.first > 0) S += '1';
else S += '0';
idx.pb(el.second);
}
ll ans = inf;
if(false){
string now = "10";
rep(i,0,N){
vi cand;
rep(j,0,2){
if(now[j] != S[i]) cand.pb(j);
}
if(cand.empty()) goto XYZ;
now[cand[0]] = S[i];
}
now = "10";
binary_indexed_tree<ll> remain(N+1);
rep(i,0,N) remain.add(idx[i],1);
ll cost = 0;
rep(i,0,N){
vi cand;
rep(j,0,2){
if(now[j] != S[i]) cand.pb(j);
}
if(cand.empty()) goto XYZ;
if(cand.size() == 2){
if(i+1 == N){
remain.add(idx[i], -1);
break;
}
else if(S[i+1] == S[i]){
now[0] = now[1] = S[i];
remain.add(idx[i], -1);
remain.add(idx[i+1], -1);
cost += remain.sum(N)-remain.sum(std::max(idx[i], idx[i+1]));
cost += remain.sum(std::min(idx[i], idx[i+1]));
i++;
}
else if(S[i+1] != '2'){
remain.add(idx[i], -1);
remain.add(idx[i+1], -1);
ll l = 0, r = 0;
l += remain.sum(N)-remain.sum(idx[i]);
l += remain.sum(N)-remain.sum(idx[i+1]);
if(idx[i+1] > idx[i]) l++;
r += remain.sum(idx[i+1]);
r += remain.sum(idx[i]);
if(idx[i] > idx[i+1]) r++;
cost += std::min(l, r);
i++;
}
else{
remain.add(idx[i], -1);
remain.add(idx[i+1], -1);
break;
}
}
else{
assert(i == 0);
remain.add(idx[i], -1);
if(S[i] == '0'){
now[0] = '0';
cost += remain.sum(idx[i]);
}
else{
now[1] = '1';
cost += remain.sum(N)-remain.sum(idx[i]);
}
}
}
ans = std::min(ans, cost);
}
XYZ:;
{
string now = "11";
rep(i,0,N){
vi cand;
rep(j,0,2){
if(now[j] != S[i]) cand.pb(j);
}
if(cand.empty()) goto WXY;
now[cand[0]] = S[i];
}
now = "11";
binary_indexed_tree<ll> remain(N+1);
rep(i,0,N) remain.add(idx[i],1);
ll cost = 0;
rep(i,0,N){
vi cand;
rep(j,0,2){
if(now[j] != S[i]) cand.pb(j);
}
if(cand.empty()) goto XYZ;
if(cand.size() == 2){
if(i+1 == N){
remain.add(idx[i], -1);
}
else if(S[i+1] == S[i]){
now[0] = now[1] = S[i];
remain.add(idx[i], -1);
remain.add(idx[i+1], -1);
cost += remain.sum(N)-remain.sum(std::max(idx[i], idx[i+1]));
cost += remain.sum(std::min(idx[i], idx[i+1]));
i++;
}
else if(S[i+1] != '2'){
remain.add(idx[i], -1);
remain.add(idx[i+1], -1);
ll l = 0, r = 0;
l += remain.sum(N)-remain.sum(idx[i]);
l += remain.sum(N)-remain.sum(idx[i+1]);
if(idx[i+1] > idx[i]) l++;
r += remain.sum(idx[i+1]);
r += remain.sum(idx[i]);
if(idx[i] > idx[i+1]) r++;
cost += std::min(l, r);
i++;
}
else{
remain.add(idx[i], -1);
remain.add(idx[i+1], -1);
break;
}
}
else{
assert(false);
}
}
ans = std::min(ans, cost);
}
WXY:;
if(ans == inf) ans = -1;
cout << ans << ln;
}
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: 3616kb
input:
10 1 1 1 1 1 -1 -1 -1 1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #2:
score: -3
Wrong Answer
time: 0ms
memory: 3836kb
input:
10 1 1 1 1 1 1 -1 1 1 -1
output:
-1
result:
wrong answer 1st numbers differ - expected: '3', found: '-1'
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: 0ms
memory: 3584kb
input:
10 3 10 5 -9 7 2 -6 1 8 0
output:
-1
result:
ok 1 number(s): "-1"
Test #61:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
10 -9 0 -1 7 5 10 6 3 2 -8
output:
13
result:
ok 1 number(s): "13"
Test #62:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
2000 40667 -598150 -1084780 1201651 1570514 -1859539 -2029075 2941581 -2945945 3038404 3447919 5293872 -5335692 -5669647 5973784 6041345 6346915 -7222112 8820986 -9153143 9563103 9749206 -9894732 -11847193 11987150 12161864 13336572 13528051 -13722732 -13836176 -15497141 -15841563 15862227 16618123 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #63:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
2000 3038404 -798315545 693574695 172661079 516504064 164016456 193562146 -131746730 382134316 -398886978 188767854 -834289064 -965673210 -826409444 -281381674 450991903 -592752625 81651101 -594873306 -352059270 -651772982 540062674 -769881300 68999588 307151563 -129950325 550154987 354801227 840540...
output:
658039
result:
ok 1 number(s): "658039"
Test #64:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
2000 -1095 -925 -1049 -1519 951 -1673 -776 345 -38 -1735 -276 -1730 123 -1629 -1896 -1576 -1115 1145 15 797 -948 287 1487 1195 1269 -1240 -1571 -275 -1915 -369 -1221 -1590 -1392 -100 1688 -1287 -241 1130 -1375 -965 669 -147 -307 -795 -1207 1939 120 -305 -915 -1078 -1448 1458 -603 1935 658 774 1471 7...
output:
668545
result:
ok 1 number(s): "668545"
Test #65:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
2000 1290 1487 -1947 -255 457 -1202 1313 36 -1511 898 1739 987 1809 -1986 -1015 -1127 -703 -223 179 557 199 349 1099 -259 -1401 -1244 -1116 646 -295 1713 1512 127 -1660 343 -1921 -1326 -549 831 1963 -1743 1655 -698 1792 366 1517 -51 404 -1853 -1295 1652 -130 -1562 -1850 -582 1504 1888 822 -24 1807 9...
output:
663841
result:
ok 1 number(s): "663841"
Test #66:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
2000 56 -1667 -1636 -671 -1311 348 976 1381 -710 -477 -1301 756 -510 495 -1215 -278 1134 950 59 1739 -33 -839 -862 605 761 827 -1708 -1180 -607 1624 -120 -1198 624 -1237 -1874 1788 1005 -331 1266 -467 -1213 1736 -182 594 775 1209 -832 300 1188 -994 -191 -217 1360 -1907 71 436 1294 -590 913 -747 -629...
output:
667052
result:
ok 1 number(s): "667052"
Test #67:
score: -4
Wrong Answer
time: 1ms
memory: 3704kb
input:
1999 -758656 -113741 -374719 7680 -227905 -201318 -200890 -84484 777096 -167712 -126972 -244117 835074 161027 923025 -224756 973701 36622 -913757 -920737 -976062 461264 147694 -162457 358437 -308202 385370 808271 -523703 -303454 -522131 -664739 -505124 306509 948216 948694 -467953 -768055 769796 486...
output:
-1
result:
wrong answer 1st numbers differ - expected: '675957', found: '-1'
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%