Submission #382496

#TimeUsernameProblemLanguageResultExecution timeMemory
382496BlancaHMTopovi (COCI15_topovi)C++14
0 / 120
645 ms37356 KiB
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long int ll;

int N, K, P;
long long int attacked;
map<pair<int, int>, int> rooks;
unordered_map<int, int> valRows, valCols, rowXOR, colXOR;

void init() {
	attacked = 0;
	valRows[0] = N;
	valCols[0] = N;
}

void include(int r, int c, int p) {
	int xorRow = 0, xorCol = 0;
	if (colXOR.find(c) != colXOR.end())
		xorCol = colXOR[c];
	if (rowXOR.find(r) != rowXOR.end())
		xorRow = rowXOR[r];
	attacked -= (ll) (N - valRows[xorCol]);
	attacked -= (ll) (N - valCols[xorRow]);
	valRows[xorRow]--;
	valCols[xorCol]--;
	rooks[{r, c}] = p;
	xorRow ^= p;
	xorCol ^= p;
	if (xorRow > 0) rowXOR[r] = xorRow;
	if (xorCol > 0) colXOR[c] = xorCol;
	valRows[xorRow]++;
	valCols[xorCol]++;
	attacked += (ll) (N - valRows[xorCol]);
	attacked += (ll) (N - valCols[xorRow]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int r, c, p, r2, c2;
	cin >> N >> K >> P;
	init();
	for (int i = 0; i < K; i++) {
		cin >> r >> c >> p;
		include(r-1, c-1, p);
	}
	for (int i = 0; i < P; i++) {
		cin >> r >> c >> r2 >> c2;
		p = rooks[{r-1, c-1}];
		include(r-1, c-1, p);
		include(r2-1, c2-1, p);
		cout << attacked << '\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...