提出 #76079528

---

ソースコード 拡げる

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        
        int[] totalAdded = new int[n + 1];
        
        int[] freqOfTotal = new int[n + q + 2];
        freqOfTotal[0] = n; 
        
        int[] suffixCount = new int[n + q + 2];
        suffixCount[0] = n; 
        
        int removedBlocks = 0; 
        int zeroCount = n;   
        
        StringBuilder output = new StringBuilder();
        
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            
            if (type == 1) {
                int x = val;
                int currentBlocks = totalAdded[x] - removedBlocks;
                
                if (currentBlocks == 0) {
                    zeroCount--;
                }
                
                int oldTotal = totalAdded[x];
                totalAdded[x]++;
                int newTotal = totalAdded[x];
                
                freqOfTotal[oldTotal]--;
                freqOfTotal[newTotal]++;
    
                suffixCount[newTotal]++;
   
                if (zeroCount == 0) {
                    removedBlocks++;
                    zeroCount = freqOfTotal[removedBlocks];
                }
                
            } else {
                int y = val;
            
                int targetTotal = y + removedBlocks;
                
                if (targetTotal >= suffixCount.length) {
                    output.append(0).append("\n");
                } else {
                    output.append(suffixCount[targetTotal]).append("\n");
                }
            }
        }
        
        System.out.print(output);
    }
}

提出情報

ジャッジ結果