f@ck1ngCumm1ng

2614

Erase_easy
OI
aaaa不了c
AuroraY
RyanMoriarty

1s乖ヽ嫁莪

3.1415926535897932384
zombotany
liuxiaocs

zmj2008

lixiaoqian

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
while (k-- > 0) {
System.out.println(binarySearch(arr, 0, n - 1, idx, true) + " " + binarySearch(arr, 0, n - 1, idx, false));
}
}

public static int binarySearch(int[] arr, int l, int r, int k, boolean left) {
while (l <= r) {
int mid = l + r >> 1;
if (arr[mid] < k) {
l = mid + 1;
} else if (arr[mid] > k) {
r = mid - 1;
} else {
if (left) {
if (mid == 0 || arr[mid - 1] != k) {
return mid;
} else {
r = mid - 1;
}
} else {
if (mid == arr.length - 1 || arr[mid + 1] != k) {
return mid;
} else {
l = mid + 1;
}
}
}
}
return -1;
}
}


import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

static int[] cnt;
static long ans = 0L;
public static void main(String[] args) throws IOException {
cnt = new int[arr.length];
mergeSort(arr, 0, arr.length);
System.out.println(ans);
}

public static void mergeSort(int[] arr, int l, int r) {
if (l >= r - 1) {
return;
}
int m = (l + r) >>> 1;
mergeSort(arr, l, m);
mergeSort(arr, m, r);
int[] tmp = new int[r - l];
int a = l;
int b = m;
for (int i = 0; i < r - l; i++) {
if (a >= m) {
tmp[i] = arr[b++];
} else if (b >= r) {
tmp[i] = arr[a++];
} else {
boolean flag = arr[a] <= arr[b];
ans += flag ? 0 : m - a;
tmp[i] = flag ? arr[a++] : arr[b++];
}
}
System.arraycopy(tmp, 0, arr, l, r - l);
}

}


import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

static int[] cnt;
static long ans = 0L;
public static void main(String[] args) throws IOException {
cnt = new int[arr.length];
mergeSort(arr, 0, arr.length);
System.out.println(ans);
}

public static void mergeSort(int[] arr, int l, int r) {
if (l >= r - 1) {
return;
}
int m = (l + r) >>> 1;
mergeSort(arr, l, m);
mergeSort(arr, m, r);
int[] tmp = new int[r - l];
int a = l;
int b = m;
for (int i = 0; i < r - l; i++) {
if (a >= m) {
tmp[i] = arr[b++];
} else if (b >= r) {
tmp[i] = arr[a++];
} else {
boolean flag = arr[a] <= arr[b];
ans += flag ? 0 : m - a;
tmp[i] = flag ? arr[a++] : arr[b++];
}
}
System.arraycopy(tmp, 0, arr, l, r - l);
}

}


import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) throws IOException {
mergeSort(arr, 0, arr.length);
for (int n : arr) {
System.out.print(n + " ");
}

}
public static void mergeSort(int[] arr, int l, int r) {
if (l >= r - 1) {
return;
}
int m = (l + r) >>> 1;
mergeSort(arr, l, m);
mergeSort(arr, m, r);

int[] tmp = new int[r - l];
int left = l;
int right = m;
for (int i = 0; i < r - l; i++) {
if (left >= m) {
tmp[i] = arr[right++];
continue;
}
if (right >= r) {
tmp[i] = arr[left++];
continue;
}
if (arr[left] <= arr[right]) {
tmp[i] = arr[left++];
} else {
tmp[i] = arr[right++];
}
}
System.arraycopy(tmp, 0, arr, l, r - l);

}
}


import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) throws IOException {
System.out.println(fuck(arr, 0, nk[0] - 1, nk[1] - 1));
}

public static int fuck(int[] arr, int l, int r, int k) {
int nxtL = l;
int nxtR = r;
int p = l;

while (l < r) {
while (l < r) {
if (arr[r] < arr[p]) {
arr[r] ^= arr[p];
arr[p] ^= arr[r];
arr[r] ^= arr[p];
p = r;
break;
}
r--;
}
while (l < r) {
if (arr[l] > arr[p]) {
arr[l] ^= arr[p];
arr[p] ^= arr[l];
arr[l] ^= arr[p];
p = l;
break;
}
l++;
}
}
if (p == k) {
return arr[p];
} else if (p < k) {
return fuck(arr, p + 1, nxtR, k);
} else {
return fuck(arr, nxtL, p - 1, k);
}
}
}


import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

// System.out.println();
public static void main(String[] args) throws IOException {
int s = Integer.parseInt(nk[0]);
int t = Integer.parseInt(nk[1]);
int[][] matrix = new int[m][2];
for (int i = 0; i < m; i++) {
}
Arrays.sort(matrix, (o1, o2) -> o1[0] - o2[0]);
if (matrix[0][0] > s) {
System.out.println(-1);
return;
}
int ans = 1;
int p = s;
int max = matrix[0][1];
for (int i = 0; i < m; i++) {
if (matrix[i][0] > max) {
System.out.println(-1);
return;
}
if (matrix[i][0] > p) {
p = max;
ans++;
}
max = Math.max(matrix[i][1], max);
if (max >= t) {
System.out.println(ans);
return;
}
}
System.out.println(-1);
}
}


TreeMapkey 存放最右侧的端点，value 存放右端点个数。

1. 如果有则他们合并，更新 TreeMap，减少一个 value 的个数（为 0 则直接删除），添加一个新的右端点入 TreeMap（这里需要用 getOrDefault 方法先查是不是已经有了，有的话需要 + 1，没有的话就是 1）；
2. 如果没有则新起一个 entry（这里需要用 getOrDefault 方法先查是不是已经有了，有的话需要 + 1，没有的话就是 1），另外 ans++
import java.util.*;
import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
}
Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
int ans = 1;
TreeMap<Integer, Integer> set = new TreeMap<>();
set.put(arr[0][1], 1);
for (int i = 1; i < n; i++) {
Map.Entry<Integer, Integer> e = set.lowerEntry(arr[i][0]);
if (e != null) {
int k = e.getKey();
int v = e.getValue();
set.remove(k);
if (v > 1) {
set.put(k, v - 1);
}
} else {
ans++;
}
int cnt = set.getOrDefault(arr[i][1], 0);
set.put(arr[i][1], cnt + 1);
}
System.out.println(ans);
}
}


import java.util.*;
import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
}
Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
int ans = 1;
TreeMap<Integer, Integer> set = new TreeMap<>();
set.put(arr[0][1], 1);
for (int i = 1; i < n; i++) {
Map.Entry<Integer, Integer> e = set.lowerEntry(arr[i][0]);
if (e != null) {
int k = e.getKey();
int v = e.getValue();
set.remove(k);
if (v > 1) {
set.put(k, v - 1);
}
} else {
ans++;
}
int cnt = set.getOrDefault(arr[i][1], 0);
set.put(arr[i][1], cnt + 1);
}
System.out.println(ans);
}
}


import java.util.*;
import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
}
Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
int ans = 1;
TreeMap<Integer, Integer> set = new TreeMap<>();
set.put(arr[0][1], 1);
for (int i = 1; i < n; i++) {
Map.Entry<Integer, Integer> e = set.lowerEntry(arr[i][0]);
if (e != null) {
int k = e.getKey();
int v = e.getValue();
set.remove(k);
if (v > 1) {
set.put(k, v - 1);
}
} else {
ans++;
}
int cnt = set.getOrDefault(arr[i][1], 0);
set.put(arr[i][1], cnt + 1);
}
System.out.println(ans);
}
}


import java.util.*;
import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
}
Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
int prev = arr[0][1];
int ans = 1;
for (int i = 1; i < n; i++) {
if (arr[i][0] > prev) {
ans++;
prev = arr[i][1];
}
}
System.out.println(ans);
}
}