Submission #87926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87926	2018-12-03T08:28:03 Z	Good	Topovi (COCI15_topovi)	C++11	120 / 120	1814 ms	64096 KB

topovi

/*
ID: blackha5
TASK: test
LANG: C++
*/
#include <bits/stdc++.h>

#define ff first
#define ss second
#define Maxn 100003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;

ll ans;
int n, k, p;

map <pii, int> E;
map <int, int> R, C;
map <int, int> cntr, cntc;

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d%d%d", &n, &k, &p);
	
	cntr[0] = n, cntc[0] = n;
	for (int i = 1; i <= k; i++) {
		int r, c, x;
		scanf ("%d%d%d", &r, &c, &x);
		
		E[{r, c}] = x;
		cntr[R[r]] --, cntc[C[c]] --;
		R[r] ^= x, C[c] ^= x;	
		cntr[R[r]] ++, cntc[C[c]] ++;
	}
	
	for (auto i: cntr)
		ans += 1ll * (n - cntc[i.ff]) * i.ss;
	
	while (p--) {
		int r1, c1;
		int r2, c2;
		
		scanf ("%d%d%d%d", &r1, &c1, &r2, &c2);
		
		int x = E[{r1, c1}];
		E[{r1, c1}] = 0;
		E[{r2, c2}] = x;
		
		ans -= n - cntc[R[r1]];
		ans -= n - cntr[C[c1]];
		if (R[r1] != C[c1])
			ans ++;
		
		cntr[R[r1]] --, cntc[C[c1]] --;
		R[r1] ^= x, C[c1] ^= x;
		cntr[R[r1]] ++, cntc[C[c1]] ++;
		
		ans += n - cntc[R[r1]];
		ans += n - cntr[C[c1]];
		if (R[r1] != C[c1])
			ans --;
		
		ans -= n - cntc[R[r2]];
		ans -= n - cntr[C[c2]];
		if (R[r2] != C[c2])
			ans ++;
		
		cntr[R[r2]] --, cntc[C[c2]] --;
		R[r2] ^= x, C[c2] ^= x;
		cntr[R[r2]] ++, cntc[C[c2]] ++;
		
		ans += n - cntc[R[r2]];
		ans += n - cntr[C[c2]];
		if (R[r2] != C[c2])
			ans --;
			
		printf ("%lld\n", ans);	
	}	
	
	return 0;
}

Compilation message

topovi.cpp: In function 'int main()':
topovi.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &k, &p);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", &r, &c, &x);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d%d", &r1, &c1, &r2, &c2);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	524 KB	Output is correct
4	Correct	3 ms	636 KB	Output is correct
5	Correct	3 ms	668 KB	Output is correct
6	Correct	173 ms	6380 KB	Output is correct
7	Correct	123 ms	6380 KB	Output is correct
8	Correct	98 ms	6380 KB	Output is correct
9	Correct	105 ms	6660 KB	Output is correct
10	Correct	122 ms	7444 KB	Output is correct
11	Correct	1567 ms	42736 KB	Output is correct
12	Correct	1796 ms	48736 KB	Output is correct
13	Correct	1783 ms	54652 KB	Output is correct
14	Correct	1814 ms	60660 KB	Output is correct
15	Correct	1744 ms	63880 KB	Output is correct
16	Correct	1664 ms	63948 KB	Output is correct
17	Correct	1450 ms	64096 KB	Output is correct
18	Correct	1535 ms	64096 KB	Output is correct
19	Correct	1492 ms	64096 KB	Output is correct
20	Correct	1717 ms	64096 KB	Output is correct