| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 436825 | 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();
//readInput();
}
static void readInput() throws IOException{
int n =readInt();
int[] a = new int[n*2];
for (int i = 0; i<n*2;i++) a[i] =readInt();
out.println(count_swaps(a));
out.close();
}
long count_swaps(int[] a) {
int n = a.length/2;
Queue<Integer>[] right = new Queue[n+1];
Queue<Integer>[] left = new Queue[n+1];
Queue<Integer> allRight = new ArrayDeque<Integer>();
segtree seg = new segtree(n*2);
for (int i = 0; i <= n; i++) {
right[i] = new ArrayDeque<Integer>();
left[i] = new ArrayDeque<Integer>();
}
for (int i = 0; i <2*n; i++) {
if (a[i] < 0) left[-a[i]].add(i);
else {
right[a[i]].add(i);
allRight.add(i);
}
}
long ans = 0 ;
for (int i= 0 ; i < 2*n; i+=2) {
int first = left[a[allRight.poll()]].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;
}
return ans;
}
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());}
}