oj.uz

Submission #100919

# Submission time Handle Problem Language Result Execution time Memory
100919 2019-03-15T07:09:34 Z cki86201 Golf (JOI17_golf) C++11
30 / 100
 2828 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; pt = zz = 0;}
	node* link[2];
	int zz, pt; int *arr;
	void update(int l, int r, int s, int e, int x) {
		if(s <= l && r <= e) {
			++zz;
			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);
		}
	}
	void init() {
		if(zz) arr = new int[zz];
		if(link[0]) link[0]->init();
		if(link[1]) link[1]->init();
	}
	
	void update2(int l, int r, int s, int e, int x) {
		if(s <= l && r <= e) {
			arr[pt++] = x;
			return;
		}
		int m = (l + r) >> 1;
		if(s <= m) link[0]->update2(l, m, s, e, x);
		if(m < e) link[1]->update2(m+1, r, s, e, x);
	}
	int read(int l, int r, int x) {
		while(pt) {
			int a = arr[--pt];
			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;
	}
};

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) H[a][x].update(0, LX, y1, y2, idx), x >>= 1;
}
void update2(int a, int x, int y1, int y2, int idx) {
	x += ADD;
	while(x) H[a][x].update2(0, LX, y1, y2, idx), x >>= 1;
}
int read(int a, int l, int r, int y) {
	l += ADD, r += ADD;
	while(l <= r) {
		if(l & 1) {
			int v = H[a][l++].read(0, LX, y);
			if(v != -1) return v;
		}
		if(!(r & 1)) {
			int v = H[a][r--].read(0, LX, 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);
		}
	}
	rep(a, 2) rep(b, 1<<19) H[a][b].init();
	
	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:196: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:197:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
golf.cpp:202: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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 36864 KB Output is correct
2 Correct 34 ms 36856 KB Output is correct
3 Correct 31 ms 36864 KB Output is correct
4 Correct 33 ms 38272 KB Output is correct
5 Correct 85 ms 52192 KB Output is correct
6 Correct 82 ms 51832 KB Output is correct
7 Correct 80 ms 50984 KB Output is correct
8 Correct 87 ms 52192 KB Output is correct
9 Correct 93 ms 51576 KB Output is correct
10 Correct 99 ms 52344 KB Output is correct
11 Correct 95 ms 52704 KB Output is correct
12 Correct 86 ms 51848 KB Output is correct
13 Correct 92 ms 51768 KB Output is correct
14 Correct 89 ms 52832 KB Output is correct
15 Correct 40 ms 40552 KB Output is correct
16 Correct 55 ms 45160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 36864 KB Output is correct
2 Correct 34 ms 36856 KB Output is correct
3 Correct 31 ms 36864 KB Output is correct
4 Correct 33 ms 38272 KB Output is correct
5 Correct 85 ms 52192 KB Output is correct
6 Correct 82 ms 51832 KB Output is correct
7 Correct 80 ms 50984 KB Output is correct
8 Correct 87 ms 52192 KB Output is correct
9 Correct 93 ms 51576 KB Output is correct
10 Correct 99 ms 52344 KB Output is correct
11 Correct 95 ms 52704 KB Output is correct
12 Correct 86 ms 51848 KB Output is correct
13 Correct 92 ms 51768 KB Output is correct
14 Correct 89 ms 52832 KB Output is correct
15 Correct 40 ms 40552 KB Output is correct
16 Correct 55 ms 45160 KB Output is correct
17 Correct 150 ms 64256 KB Output is correct
18 Correct 124 ms 64028 KB Output is correct
19 Correct 119 ms 63652 KB Output is correct
20 Correct 122 ms 63676 KB Output is correct
21 Correct 146 ms 65052 KB Output is correct
22 Correct 143 ms 64420 KB Output is correct
23 Correct 135 ms 64032 KB Output is correct
24 Correct 123 ms 63736 KB Output is correct
25 Correct 164 ms 63712 KB Output is correct
26 Correct 127 ms 63864 KB Output is correct
27 Correct 42 ms 41336 KB Output is correct
28 Correct 55 ms 45944 KB Output is correct
29 Correct 67 ms 46072 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 36864 KB Output is correct
2 Correct 34 ms 36856 KB Output is correct
3 Correct 31 ms 36864 KB Output is correct
4 Correct 33 ms 38272 KB Output is correct
5 Correct 85 ms 52192 KB Output is correct
6 Correct 82 ms 51832 KB Output is correct
7 Correct 80 ms 50984 KB Output is correct
8 Correct 87 ms 52192 KB Output is correct
9 Correct 93 ms 51576 KB Output is correct
10 Correct 99 ms 52344 KB Output is correct
11 Correct 95 ms 52704 KB Output is correct
12 Correct 86 ms 51848 KB Output is correct
13 Correct 92 ms 51768 KB Output is correct
14 Correct 89 ms 52832 KB Output is correct
15 Correct 40 ms 40552 KB Output is correct
16 Correct 55 ms 45160 KB Output is correct
17 Correct 150 ms 64256 KB Output is correct
18 Correct 124 ms 64028 KB Output is correct
19 Correct 119 ms 63652 KB Output is correct
20 Correct 122 ms 63676 KB Output is correct
21 Correct 146 ms 65052 KB Output is correct
22 Correct 143 ms 64420 KB Output is correct
23 Correct 135 ms 64032 KB Output is correct
24 Correct 123 ms 63736 KB Output is correct
25 Correct 164 ms 63712 KB Output is correct
26 Correct 127 ms 63864 KB Output is correct
27 Correct 42 ms 41336 KB Output is correct
28 Correct 55 ms 45944 KB Output is correct
29 Correct 67 ms 46072 KB Output is correct
30 Runtime error 2828 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -