| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 394144 | Agnimandur | Sails (IOI07_sails) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
import java.math.*;
import java.awt.Point;
public class Main {
//static final long MOD = 1000000007L;
//static final long MOD2 = 1000000009L;
static final long MOD = 998244353L;
//static final long INF = 500000000000L;
static final int INF = 1000000005;
static final int NINF = -1000000005;
//static final long NINF = -1000000000000000000L;
static FastScanner sc;
static PrintWriter pw;
static final int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
public static void main(String[] args) {
sc = new FastScanner();
pw = new PrintWriter(System.out);
int N = sc.ni();
int[][] sails = new int[N][2]; //H,K
for (int i = 0; i < N; i++) {
sails[i] = new int[]{sc.ni(),sc.ni()};
}
sort(sails); //increasing order of H
BinaryIndexedTree bit = new BinaryIndexedTree(100001);
for (int[] sail: sails) {
int top = bit.query(sail[0]-sail[1]);
//find the first index where "top" appears in the BIT.
int lo = 0;
int hi = 99999;
while (lo < hi) {
int m = (lo+hi)/2;
if (bit.query(m) <= top) {
hi = m;
} else {
lo = m+1;
}
}
int L = lo;
lo = 0;
hi = 99999;
while (lo < hi) {
int m = (lo+hi+1)/2;
if (bit.query(m) >= top) {
lo = m;
} else {
hi = m-1;
}
}
int R = lo;
if (R < sail[0]-1) {
int size = sail[1]-(sail[0]-1-R);
bit.update(L, L+size-1);
bit.update(R+1,sail[0]-1);
} else {
bit.update(L,L+sail[1]-1);
}
}
long ans = 0;
for (int i = 0; i < 100000; i++)
ans += solve(bit.query(i));
pw.println(ans);
pw.close();
}
public static long solve(int x) {
return (x+0L)*(x-1L)/2;
}
static class BinaryIndexedTree {
public int[] arr;
public BinaryIndexedTree (int N) {
arr = new int[N+1];
}
//add k to the i-th element.
public void add(int k, int i) {
int node = i+1;
while (node < arr.length) {
arr[node] += k;
node += node & (-node);
}
}
public void update(int L, int R) {
add(1,L);
add(-1,R+1);
}
//sum up the elements from input[s_i] to input[e_i], from [s_i,e_i].
public int sum(int s_i, int e_i) {
return sum(e_i+1) - sum(s_i);
}
public int query(int i) {
return sum(i+1);
}
private int sum(int i) {
int total = 0;
int node = i;
while (node > 0) {
total += arr[node];
node -= node & (-node);
}
return total;
}
}
public static void sort(int[] arr) {
Random rgen = new Random();
for (int i = 0; i < arr.length; i++) {
int r = rgen.nextInt(arr.length);
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
}
Arrays.sort(arr);
}
public static void sort(long[] arr) {
Random rgen = new Random();
for (int i = 0; i < arr.length; i++) {
int r = rgen.nextInt(arr.length);
long temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
}
Arrays.sort(arr);
}
//Sort an array (immune to quicksort TLE)
public static void sort(int[][] arr) {
Random rgen = new Random();
for (int i = 0; i < arr.length; i++) {
int r = rgen.nextInt(arr.length);
int[] temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0]-b[0];
}
});
}
public static void sort(long[][] arr) {
Random rgen = new Random();
for (int i = 0; i < arr.length; i++) {
int r = rgen.nextInt(arr.length);
long[] temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
}
Arrays.sort(arr, new Comparator<long[]>() {
@Override
public int compare(long[] a, long[] b) {
if (a[0] > b[0])
return 1;
else if (a[0] < b[0])
return -1;
else
return 0;
//Ascending order.
}
});
}
static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in), 32768);
st = null;
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int ni() {
return Integer.parseInt(next());
}
int[][] graph(int N, int[][] edges) {
int[][] graph = new int[N][];
int[] sz = new int[N];
for (int[] e: edges) {
sz[e[0]] += 1;
sz[e[1]] += 1;
}
for (int i = 0; i < N; i++) {
graph[i] = new int[sz[i]];
}
int[] cur = new int[N];
for (int[] e: edges) {
graph[e[0]][cur[e[0]]] = e[1];
graph[e[1]][cur[e[1]]] = e[0];
cur[e[0]] += 1;
cur[e[1]] += 1;
}
return graph;
}
int[] intArray(int N, int mod) {
int[] ret = new int[N];
for (int i = 0; i < N; i++)
ret[i] = ni()+mod;
return ret;
}
long nl() {
return Long.parseLong(next());
}
long[] longArray(int N, long mod) {
long[] ret = new long[N];
for (int i = 0; i < N; i++)
ret[i] = nl()+mod;
return ret;
}
double nd() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}