oj.uz

답안 #55185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55185 2018-07-06T08:58:44 Z 윤교준(#1528) 절취선 (JOI14_ho_t5) C++11
0 / 100
 3000 ms 19220 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int MAXN = 100005;
const int MAXX = 200055;

struct EVT {
	EVT(int type, int y, int idx)
		: type(type), y(y), idx(idx) {}
	int type, y, idx;

	bool operator < (const EVT &t) const {
		if(y != t.y) return y < t.y;
		return type < t.type;
	}
};

vector<EVT> EV;

int MC[MAXX];
set<int> VX;
unordered_set<int> VC[MAXX];

int SX[MAXN], EX[MAXN], SY[MAXN], EY[MAXN];

ll Ans;
int N, H, W;

void pushf(int x, int c) {
	MC[x] = c;
	VX.insert(x);
	VC[c].insert(x);
}

void popf(int x) {
	VX.erase(x);
	VC[MC[x]].erase(x);
	MC[x] = -1;
}

void unif(int a, int b) {
	if(a == b) return;
	if(sz(VC[a]) < sz(VC[b])) swap(a, b);

	for(int x : VC[b]) {
		VC[a].insert(x);
		MC[x] = a;
	}
	VC[b].clear();
}

int CC[MAXX];
int linef(int sx, int ex) {
	//printf("linef %d %d\n", sx, ex);
	vector<int> V;

	for(auto it = VX.lower_bound(sx); VX.end() != it && (*it) <= ex; it++) {
		V.pb(*it);
	}

	//for(int v : V) printf("%d ", v); puts("");

	if(sz(V) < 2) return 0;

	for(int v : V) CC[MC[v]] = 0;
	for(int v : V) CC[MC[v]]++;

	vector<int> CV;
	for(int v : V) CV.pb(MC[v]);
	sorv(CV); univ(CV);

	for(int i = 1; i < sz(CV); i++)
		unif(CV[0], CV[i]);

	int ret = 0;
	for(int v : CV) ret += CC[v]-1;
	return ret;
}

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	fill(MC, MC+MAXX, -1);

	cin >> W >> H >> N;
	EY[0] = EY[1] = H; SX[1] = EX[1] = W;
	SY[3] = EY[3] = H; EX[2] = EX[3] = W;
	for(int i = 0; i < N; i++)
		cin >> SX[i+4] >> SY[i+4] >> EX[i+4] >> EY[i+4];
	N += 4;

	{
		vector<int> V;
		for(int i = 0; i < N; i++) {
			V.pb(SX[i]); V.pb(EX[i]);
		}

		sorv(V); univ(V);

		for(int i = 0; i < N; i++) {
			SX[i] = (int)(lower_bound(allv(V), SX[i]) - V.begin());
			EX[i] = (int)(lower_bound(allv(V), EX[i]) - V.begin());
		}
	}
	{
		vector<int> V;
		for(int i = 0; i < N; i++) {
			V.pb(SY[i]); V.pb(EY[i]);
		}

		sorv(V); univ(V);

		for(int i = 0; i < N; i++) {
			SY[i] = (int)(lower_bound(allv(V), SY[i]) - V.begin());
			EY[i] = (int)(lower_bound(allv(V), EY[i]) - V.begin());
		}
	}

	for(int i = 0; i < N; i++) {
		if(SX[i] == EX[i]) {
			EV.eb(1, SY[i], i);
			EV.eb(3, EY[i], i);
		} else {
			EV.eb(2, SY[i], i);
		}
	}

	sorv(EV);

	for(auto &v : EV) {
		if(1 == v.type) {
			int idx = v.idx, x = SX[idx];
			pushf(x, idx);
		} else if(3 == v.type) {
			int idx = v.idx, x = SX[idx];
			popf(x);
		} else {
			int sx = SX[v.idx], ex = EX[v.idx];
			Ans += linef(sx, ex);
		}

		//printf("QUR %d %d %d\n", v.type, v.y, v.idx);
		//for(int x : VX) printf("(%d,%d) ", x, MC[x]); puts("");
		//printf("Ans=%lld\n", Ans);
	}

	cout << Ans << endl;
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12152 KB Output is correct
2 Correct 14 ms 12264 KB Output is correct
3 Correct 13 ms 12264 KB Output is correct
4 Correct 15 ms 12264 KB Output is correct
5 Correct 16 ms 12296 KB Output is correct
6 Incorrect 14 ms 12296 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12152 KB Output is correct
2 Correct 14 ms 12264 KB Output is correct
3 Correct 13 ms 12264 KB Output is correct
4 Correct 15 ms 12264 KB Output is correct
5 Correct 16 ms 12296 KB Output is correct
6 Incorrect 14 ms 12296 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 12296 KB Output is correct
2 Incorrect 15 ms 12296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12300 KB Output is correct
2 Correct 23 ms 12424 KB Output is correct
3 Correct 515 ms 13336 KB Output is correct
4 Correct 14 ms 13336 KB Output is correct
5 Correct 23 ms 13336 KB Output is correct
6 Execution timed out 3066 ms 19220 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12152 KB Output is correct
2 Correct 14 ms 12264 KB Output is correct
3 Correct 13 ms 12264 KB Output is correct
4 Correct 15 ms 12264 KB Output is correct
5 Correct 16 ms 12296 KB Output is correct
6 Incorrect 14 ms 12296 KB Output isn't correct
7 Halted 0 ms 0 KB -