답안 #89418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89418 2018-12-14T03:05:32 Z jasony123123 Topovi (COCI15_topovi) C++11
120 / 120
583 ms 29556 KB
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
inline void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/***************************************************/

// R, C
ll ans = 0;
int N;
int K, P; // initial, moves
v<pair<pii, int>> initial;
v<pair<pii, pii>> moves;
v<int> colCum, rowCum;
map<int, int> colCnt, rowCnt; // XOR value, cnt
map<pii, int> rooks;

ll contri(int r, int c) {
	ll ret = 0;
	if (rowCum[r] > 0)
		ret += N - colCum.size();
	ret += colCum.size() - colCnt[rowCum[r]];
	if (colCum[c] > 0)
		ret += N - rowCum.size();
	ret += rowCum.size() - rowCnt[colCum[c]];
	if ((colCum[c] ^ rowCum[r]))
		ret--;
	return ret;
}

void update(int r, int c, int x) {
	ans -= contri(r, c);
	rowCnt[rowCum[r]]--;
	colCnt[colCum[c]]--;
	rowCum[r] ^= x;
	colCum[c] ^= x;
	rowCnt[rowCum[r]]++;
	colCnt[colCum[c]]++;
	ans += contri(r, c);
}

void compressCoord() {
	v<int> rdat, cdat;
	for (auto& x : initial) {
		rdat.emplace_back(x.first.first);
		cdat.emplace_back(x.first.second);
	}
	for (auto& x : moves) {
		rdat.emplace_back(x.first.first);
		cdat.emplace_back(x.first.second);
		rdat.emplace_back(x.second.first);
		cdat.emplace_back(x.second.second);
	}
	sort(all(rdat));
	rdat.erase(unique(all(rdat)), rdat.end());
	sort(all(cdat));
	cdat.erase(unique(all(cdat)), cdat.end());
	for (auto& x : initial) {
		x.first.first = lower_bound(all(rdat), x.first.first) - rdat.begin();
		x.first.second = lower_bound(all(cdat), x.first.second) - cdat.begin();
	}
	for (auto& x : moves) {
		x.first.first = lower_bound(all(rdat), x.first.first) - rdat.begin();
		x.first.second = lower_bound(all(cdat), x.first.second) - cdat.begin();
		x.second.first = lower_bound(all(rdat), x.second.first) - rdat.begin();
		x.second.second = lower_bound(all(cdat), x.second.second) - cdat.begin();
	}
	colCum.resize(cdat.size());
	rowCum.resize(rdat.size());
}

int main() {
	io();
	cin >> N >> K >> P;
	initial.resize(K);
	moves.resize(P);
	FOR(i, 0, K) {
		cin >> initial[i].first.first >> initial[i].first.second >> initial[i].second;
	}
	FOR(i, 0, P) {
		cin >> moves[i].first.first >> moves[i].first.second >> moves[i].second.first >> moves[i].second.second;
	}
	compressCoord();

/*	FOR(i, 0, K) {
		cout << " " << initial[i].first.first << " " << initial[i].first.second << " " << initial[i].second << "\n";
	}
	FOR(i, 0, P) {
		cout << " " << moves[i].first.first << " " << moves[i].first.second << " " << moves[i].second.first << " " << moves[i].second.second << "\n";
	}*/

	rowCnt[0] = rowCum.size();
	colCnt[0] = colCum.size();

	for (auto& op : initial) {
		update(op.first.first, op.first.second, op.second);
		rooks[op.first] = op.second;
	}
	for (auto &op : moves) {
		auto it = rooks.find(op.first);
		int x = it->second;
		rooks.erase(it);
		update(op.first.first, op.first.second, x);
		update(op.second.first, op.second.second, x);
		rooks[op.second] = x;
		cout << ans << "\n";
	}
	return 0;
}

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 58 ms 2904 KB Output is correct
7 Correct 48 ms 3596 KB Output is correct
8 Correct 39 ms 3784 KB Output is correct
9 Correct 41 ms 4272 KB Output is correct
10 Correct 44 ms 4804 KB Output is correct
11 Correct 582 ms 21896 KB Output is correct
12 Correct 583 ms 27880 KB Output is correct
13 Correct 580 ms 29432 KB Output is correct
14 Correct 542 ms 29556 KB Output is correct
15 Correct 469 ms 29556 KB Output is correct
16 Correct 486 ms 29556 KB Output is correct
17 Correct 516 ms 29556 KB Output is correct
18 Correct 474 ms 29556 KB Output is correct
19 Correct 552 ms 29556 KB Output is correct
20 Correct 540 ms 29556 KB Output is correct