oj.uz

Submission #94442

# Submission time Handle Problem Language Result Execution time Memory
94442 2019-01-18T13:38:05 Z zeyad49 Topovi (COCI15_topovi) Java 11
42 / 120
 642 ms 66560 KB 
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

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

Subtask #1
42.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9844 KB Output is correct
2 Correct 79 ms 10104 KB Output is correct
3 Correct 77 ms 9844 KB Output is correct
4 Correct 81 ms 9972 KB Output is correct
5 Correct 81 ms 9960 KB Output is correct
6 Runtime error 414 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 642 ms 59924 KB Output is correct
8 Correct 608 ms 65260 KB Output is correct
9 Runtime error 405 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 377 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 87 ms 12040 KB Execution failed because the return code was nonzero
12 Runtime error 89 ms 11880 KB Execution failed because the return code was nonzero
13 Runtime error 88 ms 12024 KB Execution failed because the return code was nonzero
14 Runtime error 98 ms 12144 KB Execution failed because the return code was nonzero
15 Runtime error 85 ms 11896 KB Execution failed because the return code was nonzero
16 Runtime error 95 ms 12028 KB Execution failed because the return code was nonzero
17 Runtime error 94 ms 12012 KB Execution failed because the return code was nonzero
18 Runtime error 90 ms 12036 KB Execution failed because the return code was nonzero
19 Runtime error 107 ms 11928 KB Execution failed because the return code was nonzero
20 Runtime error 96 ms 11944 KB Execution failed because the return code was nonzero