oj.uz

답안 #100922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100922 2019-03-15T07:29:58 Z cki86201 Golf (JOI17_golf) C++11
30 / 100
 3780 ms 1048580 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

struct rect {
	rect(){}
	rect(int x1, int x2, int y1, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}
	int x1, x2, y1, y2;
};
struct seg {
	seg(){}
	seg(int x1, int x2, int y, int c) : x1(x1), x2(x2), y(y), c(c) {}
	int x1, x2, y, c;
	bool operator<(const seg &rhs)const {
		if(y != rhs.y) return y < rhs.y;
		return c < rhs.c;
	}
};
pii LR[400040];

vector <seg> V;
vector <int> vx, vy;
rect P[100010];
int N, cs, LX;
int T[1<<19];

void update_t2(int rt, int l, int r, int s, int e, int val) {
	if(s <= l && r <= e) {
		T[rt] = val; return;
	}
	if(T[rt]) {
		T[rt<<1] = T[rt];
		T[rt<<1|1] = T[rt];
		T[rt] = 0;
	}
	int m = (l + r) >> 1;
	if(s <= m) update_t2(rt<<1, l, m, s, e, val);
	if(m < e) update_t2(rt<<1|1, m+1, r, s, e, val);
}
int read_t2(int rt, int l, int r, int x) {
	if(l == r) return T[rt];
	if(T[rt] != 0) return T[rt];
	int m = (l + r) >> 1;
	if(x <= m) return read_t2(rt<<1, l, m, x);
	else return read_t2(rt<<1|1, m+1, r, x);
}

void update_t(int l, int r, int val) {
	if(l <= r) update_t2(1, 0, LX, l, r, val);
}

int read_t(int x) {
	return read_t2(1, 0, LX, x);
}

void flip_xy() {
	swap(vx, vy); for(int i=1;i<=N;i++) swap(P[i].x1, P[i].y1), swap(P[i].x2, P[i].y2);
}
void get_line(int cmd) {
	for(int i=1;i<=N;i++) {
		V.pb(seg(P[i].x1+1, P[i].x2-1, P[i].y2, 1));
		V.pb(seg(P[i].x1, 4*i+cmd, P[i].y1, -1));
		V.pb(seg(P[i].x2, 4*i+1+cmd, P[i].y1, -1));
	}
	sort(all(V));
	for(auto &s : V) {
		if(s.c < 0) {
			LR[s.x2].Fi = read_t(s.x1);
		}
		else {
			update_t(s.x1, s.x2, s.y);
		}
	}
	memset(T, 0, sizeof T); V.clear();
	
	for(int i=1;i<=N;i++) {
		V.pb(seg(P[i].x1+1, P[i].x2-1, -P[i].y1, 1));
		V.pb(seg(P[i].x1, 4*i+cmd, -P[i].y2, -1));
		V.pb(seg(P[i].x2, 4*i+1+cmd, -P[i].y2, -1));
	}
	sort(all(V));
	for(auto &s : V) {
		if(s.c < 0) {
			int v = -read_t(s.x1);
			if(v == 0) v = LX;
			LR[s.x2].Se = v;
		}
		else {
			update_t(s.x1, s.x2, s.y);
		}
	}
	memset(T, 0, sizeof T); V.clear();
}

int dis[400040];
struct node {
	node(){link[0] = link[1] = 0;}
	node* link[2];
	vector <int> v;
	void update(int l, int r, int s, int e, int x) {
		if(s <= l && r <= e) {
			v.pb(x);
			return;
		}
		int m = (l + r) >> 1;
		if(s <= m) {
			if(!link[0]) link[0] = new node();
			link[0]->update(l, m, s, e, x);
		}
		if(m < e) {
			if(!link[1]) link[1] = new node();
			link[1]->update(m+1, r, s, e, x);
		}
	}
	int read(int l, int r, int x) {
		while(szz(v)) {
			int a = v.back(); v.pop_back();
			if(dis[a] == -1) return a;
		}
		if(l == r) return -1;
		int m = (l + r) >> 1;
		if(x <= m) return link[0]?link[0]->read(l, m, x):-1;
		else return link[1]?link[1]->read(m+1, r, x):-1;
	}
};

const int JJ = 26;
int CH[2][1<<19];
vector <t3> lg[2][1<<19];
node H[2][1<<19]; const int ADD = 1<<18;
void update(int a, int x, int y1, int y2, int idx) {
	x += ADD;
	while(x) CH[a][x]++, x >>= 1;
}
void update2(int a, int x, int y1, int y2, int idx) {
	x += ADD;
	while(x) {
		if(CH[a][x] > JJ) H[a][x].update(0, LX, y1, y2, idx);
		else lg[a][x].pb(t3(y1, y2, idx));
		x >>= 1;
	}
}
int get_idx(int a, int rt, int y) {
	if(CH[a][rt] > JJ) return H[a][rt].read(0, LX, y);
	else {
		rep(i, szz(lg[a][rt])) {
			int y1, y2, idx;
			tie(y1, y2, idx) = lg[a][rt][i];
			if(dis[idx] != -1) {
				swap(lg[a][rt][i], lg[a][rt].back());
				lg[a][rt].pop_back();
				--i; continue;
			}
			if(y1 <= y && y <= y2) {
				swap(lg[a][rt][i], lg[a][rt].back());
				lg[a][rt].pop_back();
				return idx;
			}
		}
		return -1;
	}
}

int read(int a, int l, int r, int y) {
	l += ADD, r += ADD;
	while(l <= r) {
		if(l & 1) {
			int v = get_idx(a, l++, y);
			if(v != -1) return v;
		}
		if(!(r & 1)) {
			int v = get_idx(a, r--, y);
			if(v != -1) return v;
		}
		l >>= 1, r >>= 1;
	}
	return -1;
}

int pp[400040]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int main() {
	int ss, tt, uu, vv; scanf("%d%d%d%d", &ss, &tt, &uu, &vv);
	scanf("%d", &N);
	P[1] = rect(ss, ss, tt, tt);
	P[2] = rect(uu, uu, vv, vv);
	for(int i=3;i<=N+2;i++) {
		int x1, x2, y1, y2;
		scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
		P[i] = rect(x1, x2, y1, y2);
	}
	N += 2;
	for(int i=1;i<=N;i++) {
		vx.pb(P[i].x1); vx.pb(P[i].x2);
		vy.pb(P[i].y1); vy.pb(P[i].y2);
	}
	sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
	sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
	for(int i=1;i<=N;i++) {
		P[i].x1 = (int)(lower_bound(all(vx), P[i].x1) - vx.begin() + 1);
		P[i].x2 = (int)(lower_bound(all(vx), P[i].x2) - vx.begin() + 1);
		P[i].y1 = (int)(lower_bound(all(vy), P[i].y1) - vy.begin() + 1);
		P[i].y2 = (int)(lower_bound(all(vy), P[i].y2) - vy.begin() + 1);
	}
	LX = max(szz(vx), szz(vy)) + 1;
	
	get_line(0);
	flip_xy();
	get_line(2);
	flip_xy();
	
	/*
	 for(int i=1;i<=N;i++) {
		for(int a=0;a<4;a++) {
	 printf("%d %d\n", LR[4*i+a].Fi, LR[4*i+a].Se);
		}
	 }
	 */
	
	map <t3, int> Mx[2];
	rep(i, 4*N+5) pp[i] = i;
	for(int i=1;i<=N;i++) {
		rep(a, 4) {
			pii p = LR[4*i+a];
			t3 t;
			if(a == 0) t = t3(P[i].x1, p.Fi, p.Se);
			else if(a == 1) t = t3(P[i].x2, p.Fi, p.Se);
			else if(a == 2) t = t3(P[i].y1, p.Fi, p.Se);
			else t = t3(P[i].y2, p.Fi, p.Se);
			int ta = !!(a & 2);
			if(Mx[ta].find(t) == Mx[ta].end()) Mx[ta][t] = 4*i+a;
			else pp[Find(4*i+a)] = Find(Mx[ta][t]);
		}
	}
	
	for(int i=4;i<4*N+4;i++) if(pp[i] == i) {
		if(i&2) {
			int x = (i%4==2 ? P[i/4].y1 : P[i/4].y2);
			update(1, x, LR[i].Fi, LR[i].Se, i);
		}
		else {
			int x = (i%4==0 ? P[i/4].x1 : P[i/4].x2);
			update(0, x, LR[i].Fi, LR[i].Se, i);
		}
	}
	
	for(int i=4;i<4*N+4;i++) if(pp[i] == i) {
		if(i&2) {
			int x = (i%4==2 ? P[i/4].y1 : P[i/4].y2);
			update2(1, x, LR[i].Fi, LR[i].Se, i);
		}
		else {
			int x = (i%4==0 ? P[i/4].x1 : P[i/4].x2);
			update2(0, x, LR[i].Fi, LR[i].Se, i);
		}
	}
	
	memset(dis, -1, sizeof dis);
	vector <int> q;
	for(int i=4;i<=7;i++) {
		int pi = Find(i);
		if(dis[pi] == -1) {
			dis[pi] = 1; q.pb(pi);
		}
	}
	
	rep(i, szz(q)) {
		int t = q[i];
		while(1) {
			int v = -1;
			if(t&2) {
				int x = (t%4==2 ? P[t/4].y1 : P[t/4].y2);
				v = read(0, LR[t].Fi, LR[t].Se, x);
			}
			else {
				int x = (t%4==0 ? P[t/4].x1 : P[t/4].x2);
				v = read(1, LR[t].Fi, LR[t].Se, x);
			}
			if(v == -1) break;
			q.pb(v); dis[v] = dis[t] + 1;
		}
	}
	int ans = 1e9;
	for(int i=8;i<12;i++) {
		int pi = Find(i);
		if(dis[pi] != -1) ans = min(ans, dis[pi]);
	}
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

golf.cpp: In constructor 'rect::rect(int, int, int, int)':
golf.cpp:35:14: warning: 'rect::y1' will be initialized after [-Wreorder]
  int x1, x2, y1, y2;
              ^~
golf.cpp:35:10: warning:   'int rect::x2' [-Wreorder]
  int x1, x2, y1, y2;
          ^~
golf.cpp:34:2: warning:   when initialized here [-Wreorder]
  rect(int x1, int x2, int y1, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}
  ^~~~
golf.cpp: In function 'int main()':
golf.cpp:209:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int ss, tt, uu, vv; scanf("%d%d%d%d", &ss, &tt, &uu, &vv);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:210:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
golf.cpp:215:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 69752 KB Output is correct
2 Correct 52 ms 69712 KB Output is correct
3 Correct 57 ms 69732 KB Output is correct
4 Correct 50 ms 70392 KB Output is correct
5 Correct 98 ms 76196 KB Output is correct
6 Correct 93 ms 76200 KB Output is correct
7 Correct 87 ms 75752 KB Output is correct
8 Correct 95 ms 76280 KB Output is correct
9 Correct 87 ms 75952 KB Output is correct
10 Correct 90 ms 76360 KB Output is correct
11 Correct 88 ms 76424 KB Output is correct
12 Correct 85 ms 76024 KB Output is correct
13 Correct 86 ms 76132 KB Output is correct
14 Correct 98 ms 76412 KB Output is correct
15 Correct 65 ms 71340 KB Output is correct
16 Correct 66 ms 73216 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 69752 KB Output is correct
2 Correct 52 ms 69712 KB Output is correct
3 Correct 57 ms 69732 KB Output is correct
4 Correct 50 ms 70392 KB Output is correct
5 Correct 98 ms 76196 KB Output is correct
6 Correct 93 ms 76200 KB Output is correct
7 Correct 87 ms 75752 KB Output is correct
8 Correct 95 ms 76280 KB Output is correct
9 Correct 87 ms 75952 KB Output is correct
10 Correct 90 ms 76360 KB Output is correct
11 Correct 88 ms 76424 KB Output is correct
12 Correct 85 ms 76024 KB Output is correct
13 Correct 86 ms 76132 KB Output is correct
14 Correct 98 ms 76412 KB Output is correct
15 Correct 65 ms 71340 KB Output is correct
16 Correct 66 ms 73216 KB Output is correct
17 Correct 120 ms 80008 KB Output is correct
18 Correct 108 ms 79864 KB Output is correct
19 Correct 110 ms 79764 KB Output is correct
20 Correct 140 ms 79868 KB Output is correct
21 Correct 115 ms 80248 KB Output is correct
22 Correct 118 ms 79996 KB Output is correct
23 Correct 107 ms 79840 KB Output is correct
24 Correct 100 ms 79864 KB Output is correct
25 Correct 98 ms 79736 KB Output is correct
26 Correct 101 ms 79864 KB Output is correct
27 Correct 61 ms 71544 KB Output is correct
28 Correct 64 ms 73592 KB Output is correct
29 Correct 70 ms 73464 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 69752 KB Output is correct
2 Correct 52 ms 69712 KB Output is correct
3 Correct 57 ms 69732 KB Output is correct
4 Correct 50 ms 70392 KB Output is correct
5 Correct 98 ms 76196 KB Output is correct
6 Correct 93 ms 76200 KB Output is correct
7 Correct 87 ms 75752 KB Output is correct
8 Correct 95 ms 76280 KB Output is correct
9 Correct 87 ms 75952 KB Output is correct
10 Correct 90 ms 76360 KB Output is correct
11 Correct 88 ms 76424 KB Output is correct
12 Correct 85 ms 76024 KB Output is correct
13 Correct 86 ms 76132 KB Output is correct
14 Correct 98 ms 76412 KB Output is correct
15 Correct 65 ms 71340 KB Output is correct
16 Correct 66 ms 73216 KB Output is correct
17 Correct 120 ms 80008 KB Output is correct
18 Correct 108 ms 79864 KB Output is correct
19 Correct 110 ms 79764 KB Output is correct
20 Correct 140 ms 79868 KB Output is correct
21 Correct 115 ms 80248 KB Output is correct
22 Correct 118 ms 79996 KB Output is correct
23 Correct 107 ms 79840 KB Output is correct
24 Correct 100 ms 79864 KB Output is correct
25 Correct 98 ms 79736 KB Output is correct
26 Correct 101 ms 79864 KB Output is correct
27 Correct 61 ms 71544 KB Output is correct
28 Correct 64 ms 73592 KB Output is correct
29 Correct 70 ms 73464 KB Output is correct
30 Runtime error 3780 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -