Submission #1150209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150209		lancethedragontrainer	I want to be the very best too! (NOI17_pokemonmaster)	Java	100 / 100	4380 ms	88076 KiB

pokemonmaster

import java.io.*;
import java.util.*;
 
public class pokemonmaster {
    // --- DSU Merge Tree Structures ---
    static class MergeNode {
        int id;         // if leaf: original cell id; if internal: -1
        int mergeLevel; // for internal nodes: level at which union occurred
        int left, right; // indices of left/right children (-1 if none)
        int tin, tout;  // Euler tour time interval
    }
 
    static MergeNode[] mergeTree; // will hold up to 2*N nodes
    static int mergeTreeSize;     // current number of nodes in mergeTree
    static int[] cellToLeaf;      // maps original cell id to its leaf node index in mergeTree
 
    // DSU (without path compression, for easier rollback) used in merge tree construction.
    static class DSU {
        int[] par, sz, nodeId;
 
        DSU(int n) {
            par = new int[n];
            sz = new int[n];
            nodeId = new int[n];
            for (int i = 0; i < n; i++) {
                par[i] = i;
                sz[i] = 1;
                nodeId[i] = i; // initially, each cell is its own merge tree node
            }
        }
 
        int find(int a) {
            while (a != par[a])
                a = par[a];
            return a;
        }
    }
 
    static class Cell {
        int id, level;
    }
 
    static int R, C, N; // grid dimensions and total number of cells
 
    // --- Euler Tour Variables ---
    static int timer;
    static int[] ET;      // Euler tour: maps Euler index to original cell id
    static int[] nodeAtET; // Euler tour: maps Euler index to merge tree leaf index
 
    // --- Binary Lifting (parent pointers for merge tree) ---
    static int[] parentMT; // parent pointer for each mergeTree node
 
    // --- Mo's Algorithm with Modifications ---
    static class MoQuery {
        int L, R, time, idx; // query on Euler interval [L, R) at update time, original query index
 
        MoQuery(int L, int R, int time, int idx) {
            this.L = L;
            this.R = R;
            this.time = time;
            this.idx = idx;
        }
    }
 
    static class UpdateOp {
        int pos, prevVal, newVal;
 
        UpdateOp(int pos, int prevVal, int newVal) {
            this.pos = pos;
            this.prevVal = prevVal;
            this.newVal = newVal;
        }
    }
 
    // For input queries: type, X, Y, and value (P for update or L for query)
    static class Query {
        int t, X, Y, v;
 
        Query(int t, int X, int Y, int v) {
            this.t = t;
            this.X = X;
            this.Y = Y;
            this.v = v;
        }
    }
 
    // Global variables for Mo’s algorithm (dynamic distinct queries)
    static int BS; // block size
    static ArrayList<MoQuery> moQueries = new ArrayList<>();
    static ArrayList<UpdateOp> updates = new ArrayList<>();
    static final int MAXP = 50000 + 5;
    static int[] freq = new int[MAXP];
    static int curDistinct = 0;
    static int[] currET; // current Euler Tour array (Pokémon types) of size N
 
    // Global pointers for current Mo window.
    static int globalCurL = 0, globalCurR = 0;
 
    // --- Functions for Mo's algorithm ---
    static void addPos(int pos) {
        int val = currET[pos];
        freq[val]++;
        if (freq[val] == 1) {
            curDistinct++;
        }
    }
 
    static void removePos(int pos) {
        int val = currET[pos];
        freq[val]--;
        if (freq[val] == 0) {
            curDistinct--;
        }
    }
 
    // When applying an update, we adjust frequency counts only if the updated index lies in the current window.
    static void applyUpdate(int updIdx) {
        UpdateOp op = updates.get(updIdx);
        int pos = op.pos;
        if (pos >= globalCurL && pos < globalCurR) {
            removePos(pos);
            currET[pos] = op.newVal;
            addPos(pos);
        } else {
            currET[pos] = op.newVal;
        }
    }
 
    static void rollbackUpdate(int updIdx) {
        UpdateOp op = updates.get(updIdx);
        int pos = op.pos;
        if (pos >= globalCurL && pos < globalCurR) {
            removePos(pos);
            currET[pos] = op.prevVal;
            addPos(pos);
        } else {
            currET[pos] = op.prevVal;
        }
    }
 
    // --- DSU Merge Tree Construction ---
    static void buildMergeTree(int[] cellLevel) {
        // Initialize mergeTree with capacity 2*N and create leaves for all cells.
        mergeTree = new MergeNode[2 * N];
        cellToLeaf = new int[N];
        for (int i = 0; i < N; i++) {
            mergeTree[i] = new MergeNode();
            mergeTree[i].id = i;
            mergeTree[i].mergeLevel = 0;
            mergeTree[i].left = -1;
            mergeTree[i].right = -1;
            mergeTree[i].tin = 0;
            mergeTree[i].tout = 0;
            cellToLeaf[i] = i;
        }
        mergeTreeSize = N;
        int nextNode = N;
 
        // Build an array of cells and sort them by level.
        Cell[] cells = new Cell[N];
        for (int i = 0; i < N; i++) {
            cells[i] = new Cell();
            cells[i].id = i;
            cells[i].level = cellLevel[i];
        }
        Arrays.sort(cells, new Comparator<Cell>() {
            public int compare(Cell a, Cell b) {
                return Integer.compare(a.level, b.level);
            }
        });
 
        DSU dsu = new DSU(N);
        boolean[] active = new boolean[N];
        int[] dr = { 1, -1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };
 
        // Activate cells in increasing order of level and union with active neighbors.
        for (Cell cell : cells) {
            int id = cell.id;
            active[id] = true;
            int r = id / C, c = id % C;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C)
                    continue;
                int nb = nr * C + nc;
                if (!active[nb])
                    continue;
                int ra = dsu.find(id), rb = dsu.find(nb);
                if (ra == rb)
                    continue;
                if (dsu.sz[ra] < dsu.sz[rb]) {
                    int temp = ra;
                    ra = rb;
                    rb = temp;
                }
                // Create a new merge tree node representing the union.
                mergeTree[nextNode] = new MergeNode();
                mergeTree[nextNode].id = -1;
                mergeTree[nextNode].mergeLevel = cell.level;
                mergeTree[nextNode].left = dsu.nodeId[ra];
                mergeTree[nextNode].right = dsu.nodeId[rb];
                mergeTree[nextNode].tin = 0;
                mergeTree[nextNode].tout = 0;
 
                dsu.par[rb] = ra;
                dsu.sz[ra] += dsu.sz[rb];
                dsu.nodeId[ra] = nextNode;
 
                nextNode++;
            }
        }
        mergeTreeSize = nextNode;
    }
 
    // --- Iterative Euler Tour on the Merge Tree ---
    // This DFS assigns tin and tout values to each mergeTree node.
    static void buildEulerTour() {
        timer = 0;
        int root = mergeTreeSize - 1; // the final merge node is the root.
 
        class Frame {
            int node, state;
            Frame(int node, int state) {
                this.node = node;
                this.state = state;
            }
        }
 
        Stack<Frame> stack = new Stack<>();
        stack.push(new Frame(root, 0));
 
        while (!stack.isEmpty()) {
            Frame top = stack.peek();
            int node = top.node;
            if (top.state == 0) {
                mergeTree[node].tin = timer;
                top.state = 1;
                if (mergeTree[node].left != -1) {
                    stack.push(new Frame(mergeTree[node].left, 0));
                    continue;
                }
            }
            if (top.state == 1) {
                top.state = 2;
                if (mergeTree[node].right != -1) {
                    stack.push(new Frame(mergeTree[node].right, 0));
                    continue;
                }
            }
            if (mergeTree[node].left == -1 && mergeTree[node].right == -1) {
                timer++;
            }
            mergeTree[node].tout = timer;
            stack.pop();
        }
 
        ET = new int[N];
        nodeAtET = new int[N];
        // Each leaf corresponds to one original cell.
        for (int i = 0; i < N; i++) {
            int leaf = cellToLeaf[i];
            ET[mergeTree[leaf].tin] = i;
            nodeAtET[mergeTree[leaf].tin] = leaf;
        }
    }
 
    // --- Build Parent Pointers for Binary Lifting ---
    static void buildParentMT() {
        parentMT = new int[mergeTreeSize];
        Arrays.fill(parentMT, -1);
        for (int i = 0; i < mergeTreeSize; i++) {
            if (mergeTree[i].left != -1) {
                parentMT[mergeTree[i].left] = i;
                parentMT[mergeTree[i].right] = i;
            }
        }
    }
 
    // Given a leaf (merge tree node index) and a level threshold L, return the DSU component node.
    static int getComponentNode(int leaf, int L, int[] gridLevel) {
        int orig = mergeTree[leaf].id; // original cell id
        if (gridLevel[orig] > L)
            return -1;
        int cur = leaf;
        while (parentMT[cur] != -1) {
            int par = parentMT[cur];
            if (mergeTree[par].mergeLevel <= L)
                cur = par;
            else
                break;
        }
        return cur;
    }
 
    // --- Main Function ---
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        N = R * C;
 
        int[] gridLevel = new int[N];
        int[] gridType = new int[N];
 
        // Read grid levels.
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                gridLevel[i * C + j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // Read Pokémon types.
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                gridType[i * C + j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // Read queries.
        Query[] queriesInput = new Query[Q];
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            queriesInput[i] = new Query(t, X, Y, v);
        }
 
        // Build DSU merge tree based on grid connectivity and levels.
        buildMergeTree(gridLevel);
        buildEulerTour();
        buildParentMT();
 
        // Prepare the base Euler Tour array: for each leaf corresponding to cell i, assign its Pokémon type.
        currET = new int[N];
        int[] baseET = new int[N];
        for (int i = 0; i < N; i++) {
            int cellId = ET[i];
            baseET[i] = gridType[cellId];
            currET[i] = baseET[i];
        }
 
        int updCount = 0;
        int[] ans = new int[Q];
 
        // Process queries in input order.
        // For type 1 queries, record the update and update our current state.
        for (int i = 0; i < Q; i++) {
            Query query = queriesInput[i];
            if (query.t == 1) {
                int cell = (query.Y - 1) * C + (query.X - 1);
                int leaf = cellToLeaf[cell];
                int pos = mergeTree[leaf].tin;
                int prevVal = currET[pos];
                updates.add(new UpdateOp(pos, prevVal, query.v));
                currET[pos] = query.v;
                updCount++;
            } else { // query.t == 2
                int cell = (query.Y - 1) * C + (query.X - 1);
                if (gridLevel[cell] > query.v) {
                    moQueries.add(new MoQuery(0, 0, updCount, i));
                } else {
                    int leaf = cellToLeaf[cell];
                    int comp = getComponentNode(leaf, query.v, gridLevel);
                    if (comp == -1) {
                        moQueries.add(new MoQuery(0, 0, updCount, i));
                    } else {
                        int Lpos = mergeTree[comp].tin;
                        int Rpos = mergeTree[comp].tout;
                        moQueries.add(new MoQuery(Lpos, Rpos, updCount, i));
                    }
                }
            }
        }
 
        // Reset currET to the base state (time 0) for Mo's algorithm.
        for (int i = 0; i < N; i++) {
            currET[i] = baseET[i];
        }
 
        // Setup Mo's algorithm.
        BS = Math.max(1, (int) Math.pow(N, 2.0 / 3));
        Collections.sort(moQueries, new Comparator<MoQuery>() {
            public int compare(MoQuery a, MoQuery b) {
                int blockA = a.L / BS, blockB = b.L / BS;
                if (blockA != blockB)
                    return blockA - blockB;
                int blockRA = a.R / BS, blockRB = b.R / BS;
                if (blockRA != blockRB)
                    return blockRA - blockRB;
                return a.time - b.time;
            }
        });
 
        Arrays.fill(freq, 0);
        curDistinct = 0;
        globalCurL = 0; 
        globalCurR = 0;
        int curL = 0, curR = 0, curT = 0;
 
        // Process each Mo query.
        for (MoQuery q : moQueries) {
            while (curT < q.time) {
                applyUpdate(curT);
                curT++;
            }
            while (curT > q.time) {
                curT--;
                rollbackUpdate(curT);
            }
            while (curR < q.R) {
                addPos(curR);
                curR++;
            }
            while (curR > q.R) {
                curR--;
                removePos(curR);
            }
            while (curL < q.L) {
                removePos(curL);
                curL++;
            }
            while (curL > q.L) {
                curL--;
                addPos(curL);
            }
            globalCurL = curL;
            globalCurR = curR;
            ans[q.idx] = curDistinct;
        }
 
        // Output answers for type-2 queries in their original order.
        for (int i = 0; i < Q; i++) {
            if (queriesInput[i].t == 2) {
                out.println(ans[i]);
            }
        }
 
        out.flush();
        out.close();
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 29 / 29