| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 436820 | bobbilyking | Arranging Shoes (IOI19_shoes) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class shoes{
public static class segtree {
long[] t;
long[] lazy;
void update(int l, int r, long a) {update(1, 0, t.length/4-1, l, r, a);}
long query(int l, int r) {return query(1,0,t.length/4-1,l,r);}
public segtree(int len) {t = new long[len*4];lazy = new long[len*4];}
void update(int v, int tl, int tr, int l, int r, long new_val) {
if (l > r) return;
if (l == tl && r == tr) {
t[v] += new_val;
lazy[v] += new_val;
}
else {
push(v);
int tm = (tl+tr)/2;
update(v*2, tl, tm, l, Integer.min(r, tm), new_val);
update(v*2+1, tm+1,tr, Integer.max(l, tm+1),r, new_val);
t[v] = t[v*2] + t[v*2+1];
}
}
void push(int v) {
lazy[v*2]+=lazy[v];
lazy[v*2+1]+=lazy[v];
t[v*2+1]+=lazy[v];
t[v*2]+=lazy[v];
lazy[v]= 0;
}
long query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = (tl+tr)/2;
push(v);
return query(v*2, tl, tm, l, Integer.min(r, tm)) + query(v*2+1, tm+1, tr, Integer.max(l, tm+1), r);
}
}
public static void main(String[] args) throws IOException {
// br = new BufferedReader(new FileReader(".in"));
// out = new PrintWriter(new FileWriter(".out"));
//new Thread(null, new (), "peepee", 1<<28).start();
int n =readInt();
Queue<Integer>[] right = new Queue[n+1];
Queue<Integer> allLeft = new ArrayDeque<Integer>();
segtree seg = new segtree(n*2);
int[] a = new int[n*2];
for (int i = 0; i <= n; i++) right[i] = new ArrayDeque<Integer>();
for (int i = 0; i <2*n; i++) {
a[i] =readInt();
if (a[i] < 0) allLeft.add(i);
else right[a[i]].add(i);
}
long ans = 0 ;
for (int i= 0 ; i < 2*n; i+=2) {
int first = allLeft.poll();
long cost = first-i + seg.query(first, first);
seg.update(0, first, 1);
int next = right[-a[first]].poll();
long cost2 = next-(i+1)+seg.query(next, next);
//System.out.println(cost + " " + cost2);
seg.update(0, next, 1);
ans+=cost+cost2;
}
out.println(ans);
out.close();
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static StringTokenizer st = new StringTokenizer("");
static String read() throws IOException{return st.hasMoreTokens() ? st.nextToken():(st = new StringTokenizer(br.readLine())).nextToken();}
static int readInt() throws IOException{return Integer.parseInt(read());}
static long readLong() throws IOException{return Long.parseLong(read());}
static double readDouble() throws IOException{return Double.parseDouble(read());}
}