oj.uz

Submission #94441

# Submission time Handle Problem Language Result Execution time Memory
94441 2019-01-18T13:33:18 Z zeyad49 Topovi (COCI15_topovi) Java 11
36 / 120
 710 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.put(key,0);
			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
36.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9976 KB Output is correct
2 Correct 92 ms 10004 KB Output is correct
3 Correct 87 ms 10232 KB Output is correct
4 Correct 93 ms 9908 KB Output is correct
5 Correct 93 ms 10144 KB Output is correct
6 Runtime error 401 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 705 ms 64584 KB Output is correct
8 Runtime error 437 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 419 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 710 ms 66316 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
11 Runtime error 127 ms 12264 KB Execution failed because the return code was nonzero
12 Runtime error 102 ms 12040 KB Execution failed because the return code was nonzero
13 Runtime error 97 ms 12064 KB Execution failed because the return code was nonzero
14 Runtime error 95 ms 12040 KB Execution failed because the return code was nonzero
15 Runtime error 96 ms 11864 KB Execution failed because the return code was nonzero
16 Runtime error 113 ms 11976 KB Execution failed because the return code was nonzero
17 Runtime error 97 ms 12128 KB Execution failed because the return code was nonzero
18 Runtime error 102 ms 12048 KB Execution failed because the return code was nonzero
19 Runtime error 94 ms 11968 KB Execution failed because the return code was nonzero
20 Runtime error 99 ms 12004 KB Execution failed because the return code was nonzero