Submission #1230738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230738		phoenix_	Meteors (POI11_met)	Java	Compilation error	0 ms	0 KiB

met

// package algorithmist.poi.meteors.parallelbinarysearch;

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

class StandardIO {
    BufferedReader br;
    StringTokenizer st;
    PrintWriter pw;

    StandardIO() {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    }

    StandardIO(String inputFile, String outputFile) throws IOException {
        br = new BufferedReader(new FileReader(inputFile));
        pw = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
    }

    String readString() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        return st.nextToken();
    }

    String readLine() {
        String s = "";

        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }

        return s;
    }

    int readInt() {
        return Integer.parseInt(readString());
    }

    long readLong() {
        return Long.parseLong(readString());
    }

    double readDouble() {
        return Double.parseDouble(readString());
    }

    public char readChar() {
        return readString().charAt(0);
    }

    public boolean readBoolean() {
        return Boolean.parseBoolean(readString());
    }

    public void print(Object obj) {
        pw.print(obj);
    }

    public void println(Object obj) {
        pw.println(obj);
    }

    public void println() {
        pw.println();
    }

    public void printf(String format, Object... args) {
        pw.printf(format, args);
    }

    public void flush() {
        pw.flush();
    }

    public void close() {
        try {
            br.close();
            pw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null) return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                return false;
            }
        }

        return true;
    }
}

class FenwickTree {
    int N;
    long[] tree;

    FenwickTree(int N) {
        this.N = N;
        tree = new long[N + 1];
    }

    void update(int idx, long v) {
        for (int x = idx + 1; x <= N; x += x & -x) {
            tree[x] += v;
        }
    }

    void rangeUpdate(int low, int high, long val) {
        update(low, val);
        update(high + 1, -val);
    }

    long query(int idx) {
        long sum = 0;

        for (int x = idx + 1; x > 0; x -= x & -x) {
            sum += tree[x];
        }

        return sum;
    }

    long query(int low, int high) {
        return query(high) - query(low - 1);
    }
}

class Task {
    int N, M, Q;
    int[] required;
    ArrayList<Integer>[] queries;
    ArrayList<Integer>[] properties;
    ArrayList<Integer>[] candidates;
    int[] L;
    int[] R;
    int[] answer;
    StandardIO f = new StandardIO();

    void readInput() {
        N = f.readInt();
        M = f.readInt();
        properties = new ArrayList[N];
        required = new int[N];

        for (int i = 0; i < N; ++i) {
            properties[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; ++i) {
            int x = f.readInt() - 1;
            properties[x].add(i);
        }

        for (int i = 0; i < N; ++i) {
            required[i] = f.readInt();
        }

        Q = f.readInt();
        queries = new ArrayList[Q];

        for (int i = 0; i < Q; ++i) {
            int low = f.readInt() - 1, high = f.readInt() - 1, a = f.readInt();
            queries[i] = new ArrayList<>(List.of(low, high, a));
        }
    }

    void solve() {
        L = new int[N];
        R = new int[N];
        answer = new int[N];
        Arrays.fill(R, Q - 1);
        Arrays.fill(answer, -1);

        boolean search = true;

        while (search) {
            search = false;
            candidates = new ArrayList[Q + 1];

            for (int i = 0; i < candidates.length; ++i) {
                candidates[i] = new ArrayList<>();
            }

            FenwickTree tree = new FenwickTree(M);

            for (int i = 0; i < N; ++i) {
                if (L[i] <= R[i]) {
                    search = true;
                    int mid = (L[i] + R[i]) / 2;
                    candidates[mid].add(i);
                }
            }

            for (int i = 0; i < Q; ++i) {
                int low = queries[i].get(0), high = queries[i].get(1), a = queries[i].get(2);

                if (low > high) {
                    tree.rangeUpdate(low, M - 1, a);
                    tree.rangeUpdate(0, high, a);
                } else {
                    tree.rangeUpdate(low, high, a);
                }

                for (int idx : candidates[i]) {
                    long sum = 0;

                    for (int p : properties[idx]) {
                        sum += tree.query(p);

                        if (sum >= required[idx]) {
                            break;
                        }
                    }

                    if (sum >= required[idx]) {
                        answer[idx] = i;
                        R[idx] = i - 1;
                    } else {
                        L[idx] = i + 1;
                    }

                    if (L[idx] <= R[idx]) {
                        search = true;
                    }
                }
            }
        }

        for (int i = 0; i < N; ++i) {
            if (answer[i] == -1) {
                f.println("NIE");
            } else {
                f.println(answer[i] + 1);
            }
        }

        f.close();
    }

    void perform() {
        readInput();
        solve();
    }
}

public class Meteors {
    public static void main(String[] args) {
        Task task = new Task();
        task.perform();
    }
}

Compilation message (stderr)

met.java:262: error: class Meteors is public, should be declared in a file named Meteors.java
public class Meteors {
       ^
Note: met.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

=======