| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1150212 | lancethedragontrainer | RMQ (NOI17_rmq) | Java | 0 ms | 0 KiB |
// For each tag A, we record the allowed interval where it must appear if it is used in a query.
int[] allowedL = new int[N];
int[] allowedR = new int[N];
Arrays.fill(allowedL, 0);
Arrays.fill(allowedR, N - 1);
boolean[] hasQuery = new boolean[N];
// We will also generate events for a sweep‐line to compute LB[].
// Each query [L, R, A] gives an add event at L and (if R+1 < N) a remove event at R+1.
int totalEvents = 2 * Q;
Event[] events = new Event[totalEvents];
int eventCount = 0;
// Temporarily store queries so we can update allowed intervals and create events.
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int L = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
int A = Integer.parseInt(st.nextToken());
// Update allowed interval for tag A.
allowedL[A] = Math.max(allowedL[A], L);
allowedR[A] = Math.min(allowedR[A], R);
hasQuery[A] = true;
events[eventCount++] = new Event(L, A, true);
if (R + 1 < N) {
events[eventCount++] = new Event(R + 1, A, false);
}
}
// Sort the events by index (and add events before remove events when indices are equal).
Arrays.sort(events, 0, eventCount);
// Compute LB[i] for positions i = 0..N-1 using a sweep-line.
// At position i, LB[i] is the maximum A among all queries covering i.
int[] LB = new int[N];
TreeMap<Integer, Integer> active = new TreeMap<>();
int idxEvent = 0;
for (int i = 0; i < N; i++) {
while (idxEvent < eventCount && events[idxEvent].index == i) {
Event e = events[idxEvent];
if (e.add) {
active.put(e.val, active.getOrDefault(e.val, 0) + 1);
} else {
int cnt = active.get(e.val);
if (cnt == 1) active.remove(e.val);
else active.put(e.val, cnt - 1);
}
idxEvent++;
}
LB[i] = active.isEmpty() ? 0 : active.lastKey();
}
// Build candidate lists for each value v: positions i with LB[i] == v.
ArrayList<ArrayList<Integer>> candidates = new ArrayList<>(N);
for (int v = 0; v < N; v++) {
candidates.add(new ArrayList<>());
}
for (int i = 0; i < N; i++) {
candidates.get(LB[i]).add(i);
}
// For each tag A that appears in a query, we must assign it to a candidate position
// in the allowed interval [allowedL[A], allowedR[A]].
int[] designatedPos = new int[N]; // designatedPos[A] holds the position chosen for tag A.
Arrays.fill(designatedPos, -1);
boolean possible = true;
for (int A = 0; A < N; A++) {
if (hasQuery[A]) {
ArrayList<Integer> list = candidates.get(A);
// Binary search in list for the smallest index >= allowedL[A]
int pos = Collections.binarySearch(list, allowedL[A]);
if (pos < 0) pos = -pos - 1;
if (pos >= list.size() || list.get(pos) > allowedR[A]) {
possible = false;
break;
}
designatedPos[A] = list.get(pos);
}
}
if (!possible) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append("-1 ");
}
out.println(sb.toString().trim());
out.close();
return;
}
// Create the result array (positions 0..N-1) and assign the designated tags.
int[] result = new int[N];
Arrays.fill(result, -1);
boolean[] usedTag = new boolean[N];
for (int A = 0; A < N; A++) {
if (hasQuery[A]) {
int pos = designatedPos[A];
result[pos] = A;
usedTag[A] = true;
}
}
// Now, for every unassigned position, we must assign an unused tag X such that X >= LB[i].
// We use a TreeSet to hold all available tags.
TreeSet<Integer> availTag = new TreeSet<>();
for (int tag = 0; tag < N; tag++) {
if (!usedTag[tag]) availTag.add(tag);
}
for (int i = 0; i < N; i++) {
if (result[i] == -1) {
Integer tag = availTag.ceiling(LB[i]);
if (tag == null) {
possible = false;
break;
}
result[i] = tag;
availTag.remove(tag);
}
}
if (!possible) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append("-1 ");
}
out.println(sb.toString().trim());
} else {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(result[i]);
if (i < N - 1) sb.append(" ");
}
out.println(sb.toString().trim());
}
out.close();
}
// Helper class for events used in the sweep-line.
static class Event implements Comparable<Event> {
int index, val;
boolean add;
public Event(int index, int val, boolean add) {
this.index = index;
this.val = val;
this.add = add;
}
public int compareTo(Event other) {
if (this.index != other.index) return this.index - other.index;
// When indices are equal, add events come before remove events.
if (this.add == other.add) return 0;
return this.add ? -1 : 1;
}
}