Submission #1150212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150212		lancethedragontrainer	RMQ (NOI17_rmq)	Java	Compilation error	0 ms	0 KiB

rmq

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

Compilation message (stderr)

rmq.java:2: error: class, interface, enum, or record expected
    int[] allowedL = new int[N];
    ^
rmq.java:3: error: class, interface, enum, or record expected
    int[] allowedR = new int[N];
    ^
rmq.java:4: error: class, interface, enum, or record expected
    Arrays.fill(allowedL, 0);
    ^
rmq.java:5: error: class, interface, enum, or record expected
    Arrays.fill(allowedR, N - 1);
    ^
rmq.java:6: error: class, interface, enum, or record expected
    boolean[] hasQuery = new boolean[N];
    ^
rmq.java:10: error: class, interface, enum, or record expected
    int totalEvents = 2 * Q;
    ^
rmq.java:11: error: class, interface, enum, or record expected
    Event[] events = new Event[totalEvents];
    ^
rmq.java:12: error: class, interface, enum, or record expected
    int eventCount = 0;
    ^
rmq.java:15: error: class, interface, enum, or record expected
    for (int i = 0; i < Q; i++) {
    ^
rmq.java:15: error: class, interface, enum, or record expected
    for (int i = 0; i < Q; i++) {
                    ^
rmq.java:15: error: class, interface, enum, or record expected
    for (int i = 0; i < Q; i++) {
                           ^
rmq.java:17: error: class, interface, enum, or record expected
        int L = Integer.parseInt(st.nextToken());
        ^
rmq.java:18: error: class, interface, enum, or record expected
        int R = Integer.parseInt(st.nextToken());
        ^
rmq.java:19: error: class, interface, enum, or record expected
        int A = Integer.parseInt(st.nextToken());
        ^
rmq.java:21: error: class, interface, enum, or record expected
        allowedL[A] = Math.max(allowedL[A], L);
        ^
rmq.java:22: error: class, interface, enum, or record expected
        allowedR[A] = Math.min(allowedR[A], R);
        ^
rmq.java:23: error: class, interface, enum, or record expected
        hasQuery[A] = true;
        ^
rmq.java:24: error: class, interface, enum, or record expected
        events[eventCount++] = new Event(L, A, true);
        ^
rmq.java:25: error: class, interface, enum, or record expected
        if (R + 1 < N) {
        ^
rmq.java:27: error: class, interface, enum, or record expected
        }
        ^
rmq.java:34: error: class, interface, enum, or record expected
    int[] LB = new int[N];
    ^
rmq.java:35: error: class, interface, enum, or record expected
    TreeMap<Integer, Integer> active = new TreeMap<>();
    ^
rmq.java:36: error: class, interface, enum, or record expected
    int idxEvent = 0;
    ^
rmq.java:37: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
    ^
rmq.java:37: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
                    ^
rmq.java:37: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
                           ^
rmq.java:40: error: class, interface, enum, or record expected
            if (e.add) {
            ^
rmq.java:42: error: class, interface, enum, or record expected
            } else {
            ^
rmq.java:44: error: class, interface, enum, or record expected
                if (cnt == 1) active.remove(e.val);
                ^
rmq.java:45: error: class, interface, enum, or record expected
                else active.put(e.val, cnt - 1);
                ^
rmq.java:46: error: class, interface, enum, or record expected
            }
            ^
rmq.java:48: error: class, interface, enum, or record expected
        }
        ^
rmq.java:50: error: class, interface, enum, or record expected
    }
    ^
rmq.java:54: error: class, interface, enum, or record expected
    for (int v = 0; v < N; v++) {
    ^
rmq.java:54: error: class, interface, enum, or record expected
    for (int v = 0; v < N; v++) {
                    ^
rmq.java:54: error: class, interface, enum, or record expected
    for (int v = 0; v < N; v++) {
                           ^
rmq.java:56: error: class, interface, enum, or record expected
    }
    ^
rmq.java:57: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
                    ^
rmq.java:57: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
                           ^
rmq.java:59: error: class, interface, enum, or record expected
    }
    ^
rmq.java:64: error: class, interface, enum, or record expected
    Arrays.fill(designatedPos, -1);
    ^
rmq.java:65: error: class, interface, enum, or record expected
    boolean possible = true;
    ^
rmq.java:66: error: class, interface, enum, or record expected
    for (int A = 0; A < N; A++) {
    ^
rmq.java:66: error: class, interface, enum, or record expected
    for (int A = 0; A < N; A++) {
                    ^
rmq.java:66: error: class, interface, enum, or record expected
    for (int A = 0; A < N; A++) {
                           ^
rmq.java:70: error: class, interface, enum, or record expected
            int pos = Collections.binarySearch(list, allowedL[A]);
            ^
rmq.java:71: error: class, interface, enum, or record expected
            if (pos < 0) pos = -pos - 1;
            ^
rmq.java:72: error: class, interface, enum, or record expected
            if (pos >= list.size() || list.get(pos) > allowedR[A]) {
            ^
rmq.java:74: error: class, interface, enum, or record expected
                break;
                ^
rmq.java:75: error: class, interface, enum, or record expected
            }
            ^
rmq.java:77: error: class, interface, enum, or record expected
        }
        ^
rmq.java:82: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
        ^
rmq.java:82: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
                        ^
rmq.java:82: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
                               ^
rmq.java:84: error: class, interface, enum, or record expected
        }
        ^
rmq.java:86: error: class, interface, enum, or record expected
        out.close();
        ^
rmq.java:87: error: class, interface, enum, or record expected
        return;
        ^
rmq.java:88: error: class, interface, enum, or record expected
    }
    ^
rmq.java:92: error: class, interface, enum, or record expected
    Arrays.fill(result, -1);
    ^
rmq.java:93: error: class, interface, enum, or record expected
    boolean[] usedTag = new boolean[N];
    ^
rmq.java:94: error: class, interface, enum, or record expected
    for (int A = 0; A < N; A++) {
    ^
rmq.java:94: error: class, interface, enum, or record expected
    for (int A = 0; A < N; A++) {
                    ^
rmq.java:94: error: class, interface, enum, or record expected
    for (int A = 0; A < N; A++) {
                           ^
rmq.java:97: error: class, interface, enum, or record expected
            result[pos] = A;
            ^
rmq.java:98: error: class, interface, enum, or record expected
            usedTag[A] = true;
            ^
rmq.java:99: error: class, interface, enum, or record expected
        }
        ^
rmq.java:105: error: class, interface, enum, or record expected
    for (int tag = 0; tag < N; tag++) {
    ^
rmq.java:105: error: class, interface, enum, or record expected
    for (int tag = 0; tag < N; tag++) {
                      ^
rmq.java:105: error: class, interface, enum, or record expected
    for (int tag = 0; tag < N; tag++) {
                               ^
rmq.java:107: error: class, interface, enum, or record expected
    }
    ^
rmq.java:108: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
                    ^
rmq.java:108: error: class, interface, enum, or record expected
    for (int i = 0; i < N; i++) {
                           ^
rmq.java:111: error: class, interface, enum, or record expected
            if (tag == null) {
            ^
rmq.java:113: error: class, interface, enum, or record expected
                break;
                ^
rmq.java:114: error: class, interface, enum, or record expected
            }
            ^
rmq.java:116: error: class, interface, enum, or record expected
            availTag.remove(tag);
            ^
rmq.java:117: error: class, interface, enum, or record expected
        }
        ^
rmq.java:122: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
        ^
rmq.java:122: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
                        ^
rmq.java:122: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
                               ^
rmq.java:124: error: class, interface, enum, or record expected
        }
        ^
rmq.java:126: error: class, interface, enum, or record expected
    } else {
    ^
rmq.java:128: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
        ^
rmq.java:128: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
                        ^
rmq.java:128: error: class, interface, enum, or record expected
        for (int i = 0; i < N; i++) {
                               ^
rmq.java:130: error: class, interface, enum, or record expected
            if (i < N - 1) sb.append(" ");
            ^
rmq.java:131: error: class, interface, enum, or record expected
        }
        ^
rmq.java:133: error: class, interface, enum, or record expected
    }
    ^
rmq.java:135: error: class, interface, enum, or record expected
}
^
89 errors

=======