oj.uz

답안 #95219

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95219 2019-01-28T16:55:36 Z zeyad49 Topovi (COCI15_topovi) Java 11
60 / 120
 929 ms 66560 KB 
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

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

Subtask #1
60.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 10232 KB Output is correct
2 Correct 91 ms 9936 KB Output is correct
3 Correct 85 ms 9916 KB Output is correct
4 Correct 91 ms 10232 KB Output is correct
5 Correct 92 ms 10232 KB Output is correct
6 Correct 608 ms 49664 KB Output is correct
7 Correct 589 ms 41276 KB Output is correct
8 Correct 397 ms 32848 KB Output is correct
9 Correct 418 ms 32416 KB Output is correct
10 Correct 424 ms 33788 KB Output is correct
11 Runtime error 884 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 880 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 882 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 855 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 847 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 929 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 895 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 820 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 852 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 899 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)