Submission #95219

#	Time	Username	Problem	Language	Result	Execution time	Memory
95219		zeyad49	Topovi (COCI15_topovi)	Java	60 / 120	929 ms	66560 KiB

topovi

import java.io.*;
import java.util.*;
 
class topovi{
	
	static  HashMap<Integer,Integer> rows,cols;
	static HashMap<Integer,Integer>cntRows,cntCols;
	static HashMap<Long,Integer> power;
	
	static long ans;
	static int n;
	static void update(int r,int c,int x) {
		// subtract all cols with xor !=original xor of row r
		int original;
		original=rows.getOrDefault(r,0);
		int y=n-cntCols.getOrDefault(original, 0);
		
		ans-=y;
		// add all cols with xor != new xor of row r
		int newXor=original^x;
		rows.put(r,newXor);
		int z=cols.getOrDefault(c,0);
		cntCols.put(z^x, cntCols.getOrDefault(z^x, 0)+1);
		cntCols.put(z, cntCols.getOrDefault(z, 0)-1);
		
		y=n-cntCols.getOrDefault(newXor,0);
		ans+=y;
		cntRows.put(original, cntRows.get(original)-1);
		// subtract all rows with xor!=original xor of column c
		original=z;
		
		y=n-1-cntRows.getOrDefault(original,0);
		ans-=y;
		newXor=original^x;
		cols.put(c, newXor);
		//add all rows with xor!=new xor
		y=n-1-cntRows.getOrDefault(newXor,0);
		ans+=y;
		z=rows.getOrDefault(r,0);
		cntRows.put(z,cntRows.getOrDefault(z, 0)+1);
	}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		n=sc.nextInt();
		int k=sc.nextInt(),p=sc.nextInt();
		rows=new HashMap();
		cols=new HashMap();
		cntRows=new HashMap();
		cntCols=new HashMap();
		
		power =new HashMap();
		while(k-->0) {
			int r=sc.nextInt()-1,c=sc.nextInt()-1,x=sc.nextInt();
			power.put(hash(r,c), x);
			rows.put(r, rows.getOrDefault(r,0)^x);
			cols.put(c, cols.getOrDefault(c,0)^x);
		}
		
		for(int y:rows.keySet()) {
			int x=rows.get(y);
			cntRows.put(x, cntRows.getOrDefault(x, 0)+1);
		}
		for(int y:cols.keySet()) {
			int x=cols.get(y);
			cntCols.put(x, cntCols.getOrDefault(x, 0)+1);
		}
		cntRows.put(0,cntRows.getOrDefault(0, 0)+n-rows.size());
		cntCols.put(0,cntCols.getOrDefault(0, 0)+n-cols.size());
		ans=0;
		for(int x:rows.keySet()) {
			int z=rows.get(x);
			ans+=n-cntCols.getOrDefault(z, 0);
		}
		long rem=n-rows.size();
		ans+=rem*n-rem*cntCols.getOrDefault(0, 0);
		
	
		while(p-->0) {
			int r1=sc.nextInt()-1,c1=sc.nextInt()-1,r2=sc.nextInt()-1,c2=sc.nextInt()-1;
			long key;
			key=hash(r1,c1);
			int x=power.get(key);
			power.remove(key);
			key=hash(r2,c2);
			power.put(key,x);
			update(r1, c1, x);
			update(r2,c2,x);
			out.println(ans);
		}
		
		out.close();
 
	}
	static long hash(int r,int c) {
		return r*1l*n+c;
	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}

Compilation message (stderr)

Note: topovi.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 60 / 120