oj.uz

Submission #100918

# Submission time Handle Problem Language Result Execution time Memory
100918 2019-03-15T07:01:56 Z cki86201 Golf (JOI17_golf) C++11
30 / 100
 3127 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;
	}
};

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;
}
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);
		}
	}
	
	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:177: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:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
golf.cpp:183: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 38 ms 45052 KB Output is correct
2 Correct 33 ms 45056 KB Output is correct
3 Correct 43 ms 45056 KB Output is correct
4 Correct 39 ms 46456 KB Output is correct
5 Correct 81 ms 60792 KB Output is correct
6 Correct 85 ms 60384 KB Output is correct
7 Correct 91 ms 59428 KB Output is correct
8 Correct 89 ms 60664 KB Output is correct
9 Correct 86 ms 60092 KB Output is correct
10 Correct 84 ms 60920 KB Output is correct
11 Correct 119 ms 61176 KB Output is correct
12 Correct 81 ms 60420 KB Output is correct
13 Correct 84 ms 60256 KB Output is correct
14 Correct 123 ms 61432 KB Output is correct
15 Correct 46 ms 48820 KB Output is correct
16 Correct 56 ms 53564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 45052 KB Output is correct
2 Correct 33 ms 45056 KB Output is correct
3 Correct 43 ms 45056 KB Output is correct
4 Correct 39 ms 46456 KB Output is correct
5 Correct 81 ms 60792 KB Output is correct
6 Correct 85 ms 60384 KB Output is correct
7 Correct 91 ms 59428 KB Output is correct
8 Correct 89 ms 60664 KB Output is correct
9 Correct 86 ms 60092 KB Output is correct
10 Correct 84 ms 60920 KB Output is correct
11 Correct 119 ms 61176 KB Output is correct
12 Correct 81 ms 60420 KB Output is correct
13 Correct 84 ms 60256 KB Output is correct
14 Correct 123 ms 61432 KB Output is correct
15 Correct 46 ms 48820 KB Output is correct
16 Correct 56 ms 53564 KB Output is correct
17 Correct 121 ms 72936 KB Output is correct
18 Correct 116 ms 72732 KB Output is correct
19 Correct 115 ms 72312 KB Output is correct
20 Correct 115 ms 72440 KB Output is correct
21 Correct 115 ms 73824 KB Output is correct
22 Correct 117 ms 73080 KB Output is correct
23 Correct 168 ms 72748 KB Output is correct
24 Correct 113 ms 72416 KB Output is correct
25 Correct 118 ms 72420 KB Output is correct
26 Correct 112 ms 72612 KB Output is correct
27 Correct 46 ms 49672 KB Output is correct
28 Correct 61 ms 54392 KB Output is correct
29 Correct 61 ms 54444 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 45052 KB Output is correct
2 Correct 33 ms 45056 KB Output is correct
3 Correct 43 ms 45056 KB Output is correct
4 Correct 39 ms 46456 KB Output is correct
5 Correct 81 ms 60792 KB Output is correct
6 Correct 85 ms 60384 KB Output is correct
7 Correct 91 ms 59428 KB Output is correct
8 Correct 89 ms 60664 KB Output is correct
9 Correct 86 ms 60092 KB Output is correct
10 Correct 84 ms 60920 KB Output is correct
11 Correct 119 ms 61176 KB Output is correct
12 Correct 81 ms 60420 KB Output is correct
13 Correct 84 ms 60256 KB Output is correct
14 Correct 123 ms 61432 KB Output is correct
15 Correct 46 ms 48820 KB Output is correct
16 Correct 56 ms 53564 KB Output is correct
17 Correct 121 ms 72936 KB Output is correct
18 Correct 116 ms 72732 KB Output is correct
19 Correct 115 ms 72312 KB Output is correct
20 Correct 115 ms 72440 KB Output is correct
21 Correct 115 ms 73824 KB Output is correct
22 Correct 117 ms 73080 KB Output is correct
23 Correct 168 ms 72748 KB Output is correct
24 Correct 113 ms 72416 KB Output is correct
25 Correct 118 ms 72420 KB Output is correct
26 Correct 112 ms 72612 KB Output is correct
27 Correct 46 ms 49672 KB Output is correct
28 Correct 61 ms 54392 KB Output is correct
29 Correct 61 ms 54444 KB Output is correct
30 Runtime error 3127 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -