Submission #1150213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150213		lancethedragontrainer	RMQ (NOI17_rmq)	Java	100 / 100	659 ms	62104 KiB

rmq

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

public class rmq {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        // For each tag A, record the allowed interval where it must appear if 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];

        // 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;

        // Process each query.
        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 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.
        // LB[i] is the maximum A among all queries covering position 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, 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 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;
            }
        }

        // For every unassigned position, assign an unused tag X such that X >= LB[i].
        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;
        }
    }
}

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33