oj.uz

Submission #94443

# Submission time Handle Problem Language Result Execution time Memory
94443 2019-01-18T13:39:57 Z zeyad49 Topovi (COCI15_topovi) Java 11
36 / 120
 698 ms 66560 KB 
import java.io.*;
import java.util.*;

class topovi{
	
	static int []rows,cols;
	static TreeMap<Integer,Integer>cntRows,cntCols;
	static TreeMap<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 TreeMap();
		cntCols=new TreeMap();
		
		power =new TreeMap();
		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
36.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10112 KB Output is correct
2 Correct 87 ms 10096 KB Output is correct
3 Correct 89 ms 10232 KB Output is correct
4 Correct 90 ms 10232 KB Output is correct
5 Correct 93 ms 10212 KB Output is correct
6 Runtime error 453 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 698 ms 60120 KB Output is correct
8 Runtime error 465 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 480 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 466 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 104 ms 11876 KB Execution failed because the return code was nonzero
12 Runtime error 100 ms 12108 KB Execution failed because the return code was nonzero
13 Runtime error 92 ms 11964 KB Execution failed because the return code was nonzero
14 Runtime error 90 ms 11988 KB Execution failed because the return code was nonzero
15 Runtime error 143 ms 12088 KB Execution failed because the return code was nonzero
16 Runtime error 104 ms 11812 KB Execution failed because the return code was nonzero
17 Runtime error 101 ms 12140 KB Execution failed because the return code was nonzero
18 Runtime error 96 ms 11860 KB Execution failed because the return code was nonzero
19 Runtime error 128 ms 11812 KB Execution failed because the return code was nonzero
20 Runtime error 99 ms 11908 KB Execution failed because the return code was nonzero