| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792649 |
2023-07-25T07:49:41 Z |
반딧불(#10051) |
Line Town (CCO23_day1problem3) |
C++17 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct segTree{
int tree[1<<20];
void init(int i, int l, int r){
tree[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = v;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = tree[i*2] + tree[i*2+1];
}
int findRight(int i, int l, int r, int x){
if(r<x || !tree[i]) return r+1;
if(l==r) return l;
int m = (l+r)>>1;
int tmp = findRight(i*2, l, m, x);
if(tmp == m+1) return findRight(i*2+1, m+1, r, x);
else return tmp;
}
int findLeft(int i, int l, int r, int x){
if(x<l || !tree[i]) return l-1;
if(l==r) return l;
int m = (l+r)>>1;
int tmp = findLeft(i*2+1, m+1, r, x);
if(tmp == m) return findLeft(i*2, l, m, x);
else return tmp;
}
} tree;
void imp(){
puts("-1");
exit(0);
}
int n;
int arr[500002];
void input();
void solve();
int main(){
input();
solve();
}
void input(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
vector<int> vec;
for(int i=1; i<=n; i++) if(arr[i]) vec.push_back(abs(arr[i]));
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int i=1; i<=n; i++){
if(!arr[i]) continue;
arr[i] = (lower_bound(vec.begin(), vec.end(), abs(arr[i])) - vec.begin() + 1) * (arr[i]<0 ? -1 : 1);
}
int odd1 = 0, even1 = 0;
for(int i=1; i<=n; i++) if(arr[i] == 1){
if(i%2) odd1++;
else even1++;
}
// if(abs(odd1 - even1) > 1) imp();
}
ll ans;
ll prf[500002], suf[500002];
int c[500002];
void flip(int x){
c[x] = -c[x];
if(1<x) tree.update(1, 1, n-1, x-1, c[x] == c[x-1]);
if(x<n) tree.update(1, 1, n-1, x, c[x] == c[x+1]);
}
void solve(){
for(int i=0; i<=n+1; i++) prf[i] = suf[i] = INF;
prf[0] = 0;
suf[n+1] = 0;
ll cnt = 0;
int MX = 0;
/// prf�� ���Ѵ�
tree.init(1, 1, n-1);
for(int i=1; i<=n; i++) c[i] = arr[i];
for(int i=1; i<n; i++) if(c[i] == c[i+1]) tree.update(1, 1, n-1, i, 1);
cnt = 0, MX = 0;
for(int i=1; i<=n; i++){
if(c[i] == -1){
if(i >= MX) prf[i] = cnt;
continue;
}
int j = tree.findRight(1, 1, n-1, i) + 1;
if(j>n) break;
MX = max(MX, j);
cnt += j-i;
flip(j), flip(i);
if(MX<=i+1) prf[++i] = cnt;
}
/// suf�� ���Ѵ�
tree.init(1, 1, n-1);
for(int i=1; i<=n; i++) c[i] = arr[i];
for(int i=1; i<n; i++) if(c[i] == c[i+1]) tree.update(1, 1, n-1, i, 1);
cnt = 0, MX = n+1;
for(int i=n; i>=1; i--){
if(c[i] == 1){
if(i <= MX) suf[i] = cnt;
continue;
}
int j = tree.findLeft(1, 1, n-1, i-1);
if(j<1) break;
MX = min(MX, j);
cnt += i-j;
flip(j), flip(i);
if(MX>=i-1) suf[--i] = cnt;
}
ans = INF;
for(int i=0; i<=n; i++) ans = min(ans, prf[i] + suf[i+1]);
printf("%lld", ans == INF ? -1 : ans);
}
Compilation message
Main.cpp: In function 'void input()':
Main.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:67:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
