So, I was recently trying to solve this problem: http://usaco.org/index.php?page=viewproblem2&cpid=231. Unfortunately I am in China right now, so I can't access pastebin or ideone. The code is at the bottom. ↵
↵
Here is an explanation of my algorithm:↵
Firstly, we store segments of empty spaces. A segment is represented as an integer in the array called "vacant". `vacant[i]` means that there is a segment without cows starting at position i and covering `vacant[i]` spaces. For example, if `vacant[5]` is equal to 2, that means there is a segment from [5, 6]. Then, we store these length values in the same way as in the vacant array, but instead in a segment tree that gives maximums.↵
↵
To handle a group of cows entering the barn, I first check if there is a space to accommodate them: if the largest free space is smaller than the group of cows, then we reject them and increment the answer. If they can fit, then I binary search with the segment tree maximum to figure out which space they should occupy, based on the statement that the cows will sit at the first location that they fit in. Then, I take the segment that they sit in and chop the beginning part (where the cows sit) off, and I modify my segment tree and vacant array.↵
↵
To handle some cows leaving the barn, I use a TreeSet (a balanced binary search tree) called "startTree" to store the start points of vacant segments. When I receive a query, I look to the left and right of the start point of the query interval, and see if I can merge those two intervals. If I can merge the intervals, then I do so and remove the merged interval from the array and segment tree and TreeSet. At the end I insert the interval into the tree.↵
↵
However, I only pass the first two test cases, then I get two WA, then I get everything else TLE. I have been looking for quite a while already, and I have found no clues.↵
↵
On WA, I have no idea what is happening.↵
↵
For TLE, it seems strange to me: the first query of cows entering takes log^2 n to process, while the second query of cows leaving takes amortized log n to process. How is it possible that I get TLE with a 4 second time limit when I only perform at most M * log^2 N ~ 110m operations? Is my code too inefficient/large constant?↵
↵
Here is the code, with comments:↵
↵
~~~~~↵
import java.io.BufferedReader;↵
import java.io.BufferedWriter;↵
import java.io.FileReader;↵
import java.io.FileWriter;↵
import java.io.PrintWriter;↵
import java.util.StringTokenizer;↵
import java.util.TreeSet;↵
↵
public class seating {↵
↵
public static void main(String[] args) throws Exception {↵
//BufferedReader r = new BufferedReader(new InputStreamReader(System.in));↵
//PrintWriter w = new PrintWriter(System.out);↵
↵
BufferedReader r = new BufferedReader(new FileReader("seating.in"));↵
PrintWriter w = new PrintWriter(new BufferedWriter(new FileWriter("seating.out")));↵
↵
StringTokenizer st = new StringTokenizer(r.readLine());↵
int n = Integer.parseInt(st.nextToken());↵
int m = Integer.parseInt(st.nextToken());↵
↵
int answer = 0;↵
Segtree segtree = new Segtree(new long[n]);↵
int[] vacant = new int[n];↵
vacant[0] = n;↵
segtree.update(0, 0, n);↵
↵
TreeSet<Integer> startTree = new TreeSet<Integer>();↵
startTree.add(0);↵
↵
for (int i = 0; i < m; i++) {↵
st = new StringTokenizer(r.readLine());↵
if (st.nextToken().equals("A")) { //Should be log^2 n↵
//group arrives↵
int size = Integer.parseInt(st.nextToken());↵
if (size > segtree.query(0, n - 1)) {↵
answer++;↵
continue;↵
}↵
//Binary search on the index for which to place this group.↵
int start =0;↵
int end = n - 1segtree.getIndex(size);↵
↵
whileif (start <== end-1) {↵
int mid = (start + end) / 2;↵
if (segtree.query(0, mid) >= size) {↵
end = mid - 1;↵
} else {↵
start = mid + 1;↵
}answer++;↵
continue;↵
}↵
↵
//the segment that has start point at integer "start" is the one that group will sit in.↵
if (size + start < n)↵
vacant[size + start] = vacant[start] - size;↵
startTree.remove(start);↵
↵
if (size + start < n && vacant[size + start] != 0) startTree.add(size + start);↵
↵
if (size + start < n)↵
segtree.update(size + start, size + start, vacant[size + start] - segtree.query(size + start, size + start));↵
segtree.update(start, start, -segtree.query(start, start));↵
↵
vacant[start] = 0;↵
} else { //Should be amortized O(log n) because each segment is only checked once, and if there are collisions the other↵
//segments get merged and shouldn't be seen again↵
↵
//get out of here cows↵
int start = Integer.parseInt(st.nextToken()) - 1;↵
int end = Integer.parseInt(st.nextToken()) - 1;↵
↵
//first check to see if we are covered.↵
if (startTree.contains(start)) {↵
if (end - start + 1 <= vacant[start]) continue;↵
startTree.remove(start);↵
vacant[start] = 0;↵
segtree.update(start, start, -segtree.query(start, start));↵
}↵
↵
boolean modified = true;↵
↵
//check to the left and right and merge any intervals↵
while (modified) {↵
modified = false;↵
Integer left = startTree.lower(start);↵
Integer right = startTree.higher(start);↵
↵
int leftend = 0;↵
int rightend = 0;↵
↵
if (left != null) leftend = vacant[left] + left - 1;↵
if (right != null) rightend = vacant[right] + right - 1;↵
if (left != null && left <= start && start <= leftend) {↵
//They intersect↵
start = Math.min(start, left);↵
end = Math.max(end, leftend);↵
modified = true;↵
startTree.remove(left);↵
segtree.update(left, left, -segtree.query(left, left));↵
vacant[left] = 0;↵
}↵
↵
if (right != null && right <= end && end <= rightend) {↵
start = Math.min(start, right);↵
end = Math.max(end, rightend);↵
modified = true;↵
startTree.remove(right);↵
segtree.update(right, right, -segtree.query(right, right));↵
vacant[right] = 0;↵
}↵
}↵
↵
startTree.add(start);↵
vacant[start] = end - start + 1;↵
segtree.update(start, start, vacant[start] - segtree.query(start, start));↵
}↵
↵
}↵
↵
w.println(answer);↵
w.flush();↵
}↵
↵
↵
public static class Segtree {↵
↵
public long[] tree; // bottom row↵
public long[] lazy;↵
public int size;↵
public boolean[] leaf;↵
public int[] index;↵
↵
public Segtree(long[] base) {↵
size = base.length;↵
tree = new long[4 * base.length + 10];↵
lazy = new long[4 * base.length + 10];↵
leaf = new boolean[4 * base.length + 10];↵
index = new int[4 * base.length + 10];↵
makeTree(1, 0, base.length - 1, base);↵
}↵
↵
public void makeTree(int current, int start, int end, long[] base) {↵
if (start == end) {↵
tree[current] = base[start];↵
leaf[current] = true;↵
index[current] = start;↵
} else {↵
int mid = (start + end) / 2;↵
makeTree(2 * current, start, mid, base);↵
makeTree(2 * current + 1, mid + 1, end, base);↵
tree[current] = Math.max(tree[2 * current], tree[2 * current + 1]);↵
}↵
}↵
↵
//[start, end]↵
public void update(int start, int end, long value) {↵
update(1, 0, size - 1, start, end, value);↵
}↵
↵
public void update(int current, int left, int right, int start, int end, long val) {↵
if (left >= start && right <= end) {↵
lazy[current] += val;↵
if (leaf[current]) {↵
tree[current] = val;↵
lazy[current] -= val;↵
}↵
} else {↵
int updateLeft = Math.max(start, left);↵
int updateRight = Math.min(end, right);↵
//sorry for the tricky stuff on the next line. It should work, but only because my updates start and end are the same↵
tree[current] = Math.max(query(current, left, right, updateLeft, updateRight) + val, Math.max(query(current, left, right, left, updateLeft - 1), query(current, left, right, updateRight + 1, right))); ↵
int mid = (left + right) / 2;↵
↵
if (mid >= start && left <= end) {↵
update(2 * current, left, mid, start, end, val);↵
}↵
↵
if (right >= start && mid + 1 <= end) {↵
update(2 * current + 1, mid + 1, right, start, end, val);↵
}↵
}↵
}↵
↵
//[start, end]↵
public long query(int start, int end) {↵
if (start > end) return 0 / 4;↵
return query(1, 0, size - 1, start, end);↵
}↵
↵
public long query(int current, int left, int right, int start, int end) {↵
if (left >= start && right <= end) {↵
if (lazy[current] != 0) {↵
tree[current] += lazy[current];↵
↵
if (2 * current < lazy.length) { //if it is not a base node↵
lazy[2 * current] += lazy[current];↵
lazy[2 * current + 1] += lazy[current];↵
}↵
lazy[current] = 0;↵
}↵
return tree[current];↵
} else {↵
tree[current] += lazy[current];↵
↵
if (2 * current < lazy.length) {↵
lazy[2 * current] += lazy[current];↵
lazy[2 * current + 1] += lazy[current];↵
}↵
↵
lazy[current] = 0;↵
int mid = (left + right) / 2;↵
long answer = 0;↵
↵
if (mid >= start && left <= end) {↵
answer = Math.max(answer, query(2 * current, left, mid, start, end));↵
}↵
if (right >= start && mid + 1 <= end) {↵
answer = Math.max(answer, query(2 * current + 1, mid + 1, right, start, end));↵
}↵
return answer;↵
}↵
}↵
}↵
↵
public int getIndex(int size) {↵
int current = 1;↵
if (tree[current] < size) return -1;↵
↵
while (!leaf[current]) {↵
if (tree[2 * current] >= size) {↵
current = 2 * current;↵
} else {↵
current = 2 * current + 1;↵
}↵
}↵
return index[current];↵
}↵
}↵
}↵
↵
~~~~~↵
↵
Please help. I would really appreciate it. Thank you!↵
↵
Edit: added a few lines, but the result didn't change.
↵
Here is an explanation of my algorithm:↵
Firstly, we store segments of empty spaces. A segment is represented as an integer in the array called "vacant". `vacant[i]` means that there is a segment without cows starting at position i and covering `vacant[i]` spaces. For example, if `vacant[5]` is equal to 2, that means there is a segment from [5, 6]. Then, we store these length values in the same way as in the vacant array, but instead in a segment tree that gives maximums.↵
↵
To handle a group of cows entering the barn, I first check if there is a space to accommodate them: if the largest free space is smaller than the group of cows, then we reject them and increment the answer. If they can fit, then I binary search with the segment tree maximum to figure out which space they should occupy, based on the statement that the cows will sit at the first location that they fit in. Then, I take the segment that they sit in and chop the beginning part (where the cows sit) off, and I modify my segment tree and vacant array.↵
↵
To handle some cows leaving the barn, I use a TreeSet (a balanced binary search tree) called "startTree" to store the start points of vacant segments. When I receive a query, I look to the left and right of the start point of the query interval, and see if I can merge those two intervals. If I can merge the intervals, then I do so and remove the merged interval from the array and segment tree and TreeSet. At the end I insert the interval into the tree.↵
↵
However, I only pass the first two test cases, then I get two WA, then I get everything else TLE. I have been looking for quite a while already, and I have found no clues.↵
↵
On WA, I have no idea what is happening.↵
↵
For TLE, it seems strange to me: the first query of cows entering takes log^2 n to process, while the second query of cows leaving takes amortized log n to process. How is it possible that I get TLE with a 4 second time limit when I only perform at most M * log^2 N ~ 110m operations? Is my code too inefficient/large constant?↵
↵
Here is the code, with comments:↵
↵
~~~~~↵
import java.io.BufferedReader;↵
import java.io.BufferedWriter;↵
import java.io.FileReader;↵
import java.io.FileWriter;↵
import java.io.PrintWriter;↵
import java.util.StringTokenizer;↵
import java.util.TreeSet;↵
↵
public class seating {↵
↵
public static void main(String[] args) throws Exception {↵
//BufferedReader r = new BufferedReader(new InputStreamReader(System.in));↵
//PrintWriter w = new PrintWriter(System.out);↵
↵
BufferedReader r = new BufferedReader(new FileReader("seating.in"));↵
PrintWriter w = new PrintWriter(new BufferedWriter(new FileWriter("seating.out")));↵
↵
StringTokenizer st = new StringTokenizer(r.readLine());↵
int n = Integer.parseInt(st.nextToken());↵
int m = Integer.parseInt(st.nextToken());↵
↵
int answer = 0;↵
Segtree segtree = new Segtree(new long[n]);↵
int[] vacant = new int[n];↵
vacant[0] = n;↵
segtree.update(0, 0, n);↵
↵
TreeSet<Integer> startTree = new TreeSet<Integer>();↵
startTree.add(0);↵
↵
for (int i = 0; i < m; i++) {↵
st = new StringTokenizer(r.readLine());↵
if (st.nextToken().equals("A")) { //Should be log
//group arrives↵
int size = Integer.parseInt(st.nextToken());↵
answer++;↵
continue;↵
}↵
int start =
int end = n - 1
↵
if (segtree.query(0, mid) >= size) {↵
end = mid - 1;↵
} else {↵
start = mid + 1;↵
}
continue;↵
}↵
↵
//the segment that has start point at integer "start" is the one that group will sit in.↵
if (size + start < n)↵
vacant[size + start] = vacant[start] - size;↵
startTree.remove(start);↵
↵
if (size + start < n && vacant[size + start] != 0) startTree.add(size + start);↵
↵
if (size + start < n)↵
segtree.update(size + start, size + start, vacant[size + start] - segtree.query(size + start, size + start));↵
segtree.update(start, start, -segtree.query(start, start));↵
↵
vacant[start] = 0;↵
} else { //Should be amortized O(log n) because each segment is only checked once, and if there are collisions the other↵
//segments get merged and shouldn't be seen again↵
↵
//get out of here cows↵
int start = Integer.parseInt(st.nextToken()) - 1;↵
int end = Integer.parseInt(st.nextToken()) - 1;↵
↵
//first check to see if we are covered.↵
if (startTree.contains(start)) {↵
if (end - start + 1 <= vacant[start]) continue;↵
startTree.remove(start);↵
vacant[start] = 0;↵
segtree.update(start, start, -segtree.query(start, start));↵
}↵
↵
boolean modified = true;↵
↵
//check to the left and right and merge any intervals↵
while (modified) {↵
modified = false;↵
Integer left = startTree.lower(start);↵
Integer right = startTree.higher(start);↵
↵
int leftend = 0;↵
int rightend = 0;↵
↵
if (left != null) leftend = vacant[left] + left - 1;↵
if (right != null) rightend = vacant[right] + right - 1;↵
if (left != null && left <= start && start <= leftend) {↵
//They intersect↵
start = Math.min(start, left);↵
end = Math.max(end, leftend);↵
modified = true;↵
startTree.remove(left);↵
segtree.update(left, left, -segtree.query(left, left));↵
vacant[left] = 0;↵
}↵
↵
if (right != null && right <= end && end <= rightend) {↵
start = Math.min(start, right);↵
end = Math.max(end, rightend);↵
modified = true;↵
startTree.remove(right);↵
segtree.update(right, right, -segtree.query(right, right));↵
vacant[right] = 0;↵
}↵
}↵
↵
startTree.add(start);↵
vacant[start] = end - start + 1;↵
segtree.update(start, start, vacant[start] - segtree.query(start, start));↵
}↵
↵
}↵
↵
w.println(answer);↵
w.flush();↵
}↵
↵
↵
public static class Segtree {↵
↵
public long[] tree; // bottom row↵
public long[] lazy;↵
public int size;↵
public boolean[] leaf;↵
public int[] index;↵
↵
public Segtree(long[] base) {↵
size = base.length;↵
tree = new long[4 * base.length + 10];↵
lazy = new long[4 * base.length + 10];↵
leaf = new boolean[4 * base.length + 10];↵
index = new int[4 * base.length + 10];↵
makeTree(1, 0, base.length - 1, base);↵
}↵
↵
public void makeTree(int current, int start, int end, long[] base) {↵
if (start == end) {↵
tree[current] = base[start];↵
leaf[current] = true;↵
index[current] = start;↵
} else {↵
int mid = (start + end) / 2;↵
makeTree(2 * current, start, mid, base);↵
makeTree(2 * current + 1, mid + 1, end, base);↵
tree[current] = Math.max(tree[2 * current], tree[2 * current + 1]);↵
}↵
}↵
↵
//[start, end]↵
public void update(int start, int end, long value) {↵
update(1, 0, size - 1, start, end, value);↵
}↵
↵
public void update(int current, int left, int right, int start, int end, long val) {↵
if (left >= start && right <= end) {↵
lazy[current] += val;↵
if (leaf[current]) {↵
tree[current] = val;↵
lazy[current] -= val;↵
}↵
} else {↵
int updateLeft = Math.max(start, left);↵
int updateRight = Math.min(end, right);↵
//sorry for the tricky stuff on the next line. It should work, but only because my updates start and end are the same↵
tree[current] = Math.max(query(current, left, right, updateLeft, updateRight) + val, Math.max(query(current, left, right, left, updateLeft - 1), query(current, left, right, updateRight + 1, right))); ↵
int mid = (left + right) / 2;↵
↵
if (mid >= start && left <= end) {↵
update(2 * current, left, mid, start, end, val);↵
}↵
↵
if (right >= start && mid + 1 <= end) {↵
update(2 * current + 1, mid + 1, right, start, end, val);↵
}↵
}↵
}↵
↵
//[start, end]↵
public long query(int start, int end) {↵
if (start > end) return 0 / 4;↵
return query(1, 0, size - 1, start, end);↵
}↵
↵
public long query(int current, int left, int right, int start, int end) {↵
if (left >= start && right <= end) {↵
if (lazy[current] != 0) {↵
tree[current] += lazy[current];↵
↵
if (2 * current < lazy.length) { //if it is not a base node↵
lazy[2 * current] += lazy[current];↵
lazy[2 * current + 1] += lazy[current];↵
}↵
lazy[current] = 0;↵
}↵
return tree[current];↵
} else {↵
tree[current] += lazy[current];↵
↵
if (2 * current < lazy.length) {↵
lazy[2 * current] += lazy[current];↵
lazy[2 * current + 1] += lazy[current];↵
}↵
↵
lazy[current] = 0;↵
int mid = (left + right) / 2;↵
long answer = 0;↵
↵
if (mid >= start && left <= end) {↵
answer = Math.max(answer, query(2 * current, left, mid, start, end));↵
}↵
if (right >= start && mid + 1 <= end) {↵
answer = Math.max(answer, query(2 * current + 1, mid + 1, right, start, end));↵
}↵
return answer;↵
}↵
}↵
public int getIndex(int size) {↵
int current = 1;↵
if (tree[current] < size) return -1;↵
↵
while (!leaf[current]) {↵
if (tree[2 * current] >= size) {↵
current = 2 * current;↵
} else {↵
current = 2 * current + 1;↵
}↵
}↵
return index[current];↵
}↵
}↵
}↵
↵
~~~~~↵
↵
Please help. I would really appreciate it. Thank you!↵
↵
Edit: added a few lines, but the result didn't change.
