| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 95219 |
2019-01-28T16:55:36 Z |
zeyad49 |
Topovi (COCI15_topovi) |
Java 11 |
|
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.
| # |
Verdict |
Execution time |
Memory |
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) |
