Submission #94442

#TimeUsernameProblemLanguageResultExecution timeMemory
94442zeyad49Topovi (COCI15_topovi)Java
42 / 120
642 ms66560 KiB

import java.io.*;
import java.util.*;

class topovi{
	
	static int []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[r];
		int y=n-cntCols.getOrDefault(original, 0);
		
		ans-=y;
		// add all cols with xor != new xor of row r
		int newXor=original^x;
		rows[r]=newXor;
		cntCols.put(cols[c]^x, cntCols.getOrDefault(cols[c]^x, 0)+1);
		cntCols.put(cols[c], cntCols.getOrDefault(cols[c], 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=cols[c];
		
		y=n-1-cntRows.getOrDefault(original,0);
		ans-=y;
		newXor=original^x;
		cols[c]=newXor;
		//add all rows with xor!=new xor
		y=n-1-cntRows.getOrDefault(newXor,0);
		ans+=y;
		cntRows.put(rows[r],cntRows.getOrDefault(rows[r], 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 int [n];
		cols=new int [n];
		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[r]^=x;
			cols[c]^=x;
		}
		
		for(int x:rows)
			cntRows.put(x, cntRows.getOrDefault(x, 0)+1);
		for(int x:cols)
			cntCols.put(x, cntCols.getOrDefault(x, 0)+1);
		

		ans=0;
		for(int i=0;i<n;i++)
		{
			int x=rows[i];
			ans+=n-cntCols.getOrDefault(x, 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.
#Verdict Execution timeMemoryGrader output
Fetching results...