Submission #1230746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230746		phoenix_	Meteors (POI11_met)	Java	0 / 100	6097 ms	131072 KiB

met

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

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

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

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

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

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

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

    // Clear the tree efficiently
    void clear() {
        Arrays.fill(tree, 0);
    }
}

class Task {
    int N, M, Q;
    long[] required;
    int[] owner;  // owner[sector] = state_id, much more memory efficient
    int[] queryL, queryR;
    long[] queryA;
    int[] L, R, answer;
    List<Integer> activeQueries; // Reuse this list instead of creating new arrays
    StandardIO f = new StandardIO();

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

        // Read sector ownership - much more memory efficient
        for (int i = 0; i < M; ++i) {
            owner[i] = f.readInt() - 1;
        }

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

        Q = f.readInt();
        queryL = new int[Q];
        queryR = new int[Q];
        queryA = new long[Q];

        for (int i = 0; i < Q; ++i) {
            queryL[i] = f.readInt() - 1;
            queryR[i] = f.readInt() - 1;
            queryA[i] = f.readLong();
        }
    }

    void solve() {
        L = new int[N];
        R = new int[N];
        answer = new int[N];
        Arrays.fill(R, Q);  // Search in range [0, Q] where Q means impossible
        Arrays.fill(answer, -1);
        
        activeQueries = new ArrayList<>();

        FenwickTree tree = new FenwickTree(M);

        while (true) {
            activeQueries.clear();
            
            // Collect active queries
            for (int i = 0; i < N; ++i) {
                if (L[i] <= R[i]) {
                    activeQueries.add(i);
                }
            }
            
            if (activeQueries.isEmpty()) break;

            // Group by mid values using simple map
            Map<Integer, List<Integer>> groups = new HashMap<>();
            for (int state : activeQueries) {
                int mid = (L[state] + R[state]) / 2;
                groups.computeIfAbsent(mid, k -> new ArrayList<>()).add(state);
            }

            // Process groups in sorted order
            List<Integer> mids = new ArrayList<>(groups.keySet());
            Collections.sort(mids);

            tree.clear();
            int currentQuery = 0;

            for (int mid : mids) {
                // Apply queries up to mid-1
                while (currentQuery < mid) {
                    int low = queryL[currentQuery];
                    int high = queryR[currentQuery];
                    long val = queryA[currentQuery];

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

                // Process all states with this mid value
                for (int state : groups.get(mid)) {
                    long sum = 0;
                    
                    // Calculate sum for this state efficiently
                    for (int sector = 0; sector < M && sum < required[state]; sector++) {
                        if (owner[sector] == state) {
                            sum += tree.query(sector);
                        }
                    }

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

        // Output results
        for (int i = 0; i < N; ++i) {
            if (answer[i] == -1 || answer[i] >= Q) {
                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: 0 / 12
• Subtask 2: 0 / 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