제출 #1230752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230752		phoenix_	새로운 문제 (POI11_met)	Java	24 / 100	6098 ms	129028 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;
    }

    void clear() {
        Arrays.fill(tree, 0);
    }
}

class Task {
    int N, M, Q;
    int[] required;
    int[] propertiesStart;
    int[] propertiesData;
    int[] queryLow;
    int[] queryHigh;
    int[] queryA;
    int[] L;
    int[] R;
    int[] answer;
    int[] candidatesForQuery;
    StandardIO f = new StandardIO();

    void readInput() {
        N = f.readInt();
        M = f.readInt();
        
        // Count total properties
        int totalProperties = 0;
        int[] tempOwners = new int[M];
        for (int i = 0; i < M; ++i) {
            tempOwners[i] = f.readInt() - 1;
            totalProperties++;
        }
        
        // Build compressed representation
        propertiesStart = new int[N + 1];
        propertiesData = new int[totalProperties];
        
        // Count properties per owner
        for (int i = 0; i < M; ++i) {
            propertiesStart[tempOwners[i] + 1]++;
        }
        
        // Convert to prefix sum
        for (int i = 1; i <= N; ++i) {
            propertiesStart[i] += propertiesStart[i - 1];
        }
        
        // Fill properties data
        int[] currentPos = Arrays.copyOf(propertiesStart, N);
        for (int i = 0; i < M; ++i) {
            int owner = tempOwners[i];
            propertiesData[currentPos[owner]++] = i;
        }
        
        required = new int[N];
        for (int i = 0; i < N; ++i) {
            required[i] = f.readInt();
        }

        Q = f.readInt();
        queryLow = new int[Q];
        queryHigh = new int[Q];
        queryA = new int[Q];
        
        for (int i = 0; i < Q; ++i) {
            queryLow[i] = f.readInt() - 1;
            queryHigh[i] = f.readInt() - 1;
            queryA[i] = f.readInt();
        }
    }

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

        boolean search = true;

        while (search) {
            search = false;
            Arrays.fill(candidatesForQuery, -1);
            tree.clear();

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

            for (int i = 0; i < Q; ++i) {
                int low = queryLow[i];
                int high = queryHigh[i];
                int a = queryA[i];

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

                // Check candidates for this query
                for (int idx = 0; idx < N; ++idx) {
                    if (candidatesForQuery[idx] == i) {
                        long sum = 0;
                        
                        for (int j = propertiesStart[idx]; j < propertiesStart[idx + 1]; ++j) {
                            sum += tree.query(propertiesData[j]);
                            
                            if (sum >= required[idx]) {
                                break;
                            }
                        }

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

        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 met {
    public static void main(String[] args) {
        Task task = new Task();
        task.perform();
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13