oj.uz

Submission #115095

# Submission time Handle Problem Language Result Execution time Memory
115095 2019-06-05T08:54:49 Z 윤교준(#2865) Iqea (innopolis2018_final_C) C++14
36 / 100
 1443 ms 190524 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MAXQ = 100055;
const int MAXK = MAXN;

int getDist(pii, pii);
int getDist(pii, int);

struct DJF {
	DJF() { init(); }
	int ud[MAXN];

	void init() { iota(ud, ud+MAXN, 0); }
	int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
	void uf(int a, int b) { ud[uf(b)] = uf(a); }
};

struct BIT {
	pii *d;
	int n;

	void init(int _n) {
		n = _n+5;
		d = new pii[n];
		fill(d, d+n, pii(INF, -1));
	}
	void upd(int x, pii r) {
		for(x += 2; x < n; x += rb(x))
			if(r < d[x]) d[x] = r;
	}
	pii get(int x) {
		pii r(INF, -1);
		for(x += 2; x; x -= rb(x))
			if(d[x] < r) r = d[x];
		return r;
	}
};

struct RMQ {
	pii d[18][MAXN*2];
	pii A[MAXN*2];
	int B[MAXN*2];
	int L;

	void cal() {
		for(int i = 0, s, e;; i++) {
			s = 1 << i; e = s << 1;
			if(L < s) break;
			for(int j = s; j < e; j++)
				B[j] = i;
		}

		for(int i = 1; i <= L; i++) d[0][i] = A[i];
		for(int j = 1; j < 18; j++) for(int i = 1, e; i <= L; i++) {
			e = i + (1 << (j-1));
			d[j][i] = e <= L ? min(d[j-1][i], d[j-1][e]) : d[j-1][i];
		}
	}

	pii get(int s, int e) {
		int k = B[e-s+1];
		return min(d[k][s], d[k][e-(1<<k)+1]);
	}
};

struct TRE {
	RMQ rmq;

	vector<int> G[MAXN];
	int dep[MAXN], AS[MAXN], AE[MAXN];
	int A[MAXN*2], An;

	void add(int a, int b) {
		G[a].eb(b);
		G[b].eb(a);
	}
	void dfs(int i) {
		A[++An] = i;
		AS[i] = An;
		for(int v : G[i]) if(!dep[v]) {
			dep[v] = dep[i] + 1;
			dfs(v);
			A[++An] = i;
		}
		AE[i] = An;
	}
	void cal() {
		for(int i = 1; i < MAXN; i++) if(!dep[i]) {
			dep[i] = 1;
			dfs(i);
		}

		rmq.L = An;
		for(int i = 1, j; i <= An; i++) {
			j = A[i];
			rmq.A[i] = pii(dep[j], j);
		}
		rmq.cal();
	}
	int lca(int a, int b) {
		pii r = rmq.get(min(AS[a], AS[b]), max(AE[a], AE[b]));
		return r.second;
	}
	int get(int a, int b) {
		return dep[a] + dep[b] - (dep[lca(a, b)] << 1);
	}
} treX, treY;

struct NOD {
	NOD() : sy(INF), ey(-INF) {}
	BIT bitu, bitd;
	int x, sy, ey;

	void init() {
		int l = ey-sy+1;
		bitu.init(l);
		bitd.init(l);
	}

	void addCell(pii p) {
		x = p.first;
		if(p.second < sy) sy = p.second;
		if(ey < p.second) ey = p.second;
	}

	int getY(pii p) {
		if(sy == ey) return sy;
		int dw = ::getDist(p, pii(x, sy));
		int up = ::getDist(p, pii(x, ey));
		int l = ey-sy;
		int t = (dw+up-l) >> 1;
		return sy + (dw-t);
	}

	void addHubo(pii p, int idx) {
		int s = getY(p), d = ::getDist(p, pii(x, s));
		bitu.upd(s-sy, pii(d-s, idx));
		bitd.upd(ey-s, pii(d+s, idx));
	}
	int get(pii p) {
		int r = INF, y = getY(p);
		pii up = bitu.get(y-sy), dp = bitd.get(ey-y);
		if(0 < up.second) {
			int t = ::getDist(p, up.second);
			if(t < r) r = t;
		}
		if(0 < dp.second) {
			int t = ::getDist(p, dp.second);
			if(t < r) r = t;
		}
		return r;
	}
} nod[MAXK];
vector<int> G[MAXK];
int prt[MAXK], cnt[MAXK];

int MPX[MAXN], MPY[MAXN], MPK[MAXN];
pii P[MAXN], PS[MAXN], QP[MAXQ];

int N, Q, K, Krt;

inline int f(const pii &p) {
	const int r = int(lower_bound(PS+1, PS+N+1, p) - PS);
	return p == PS[r] ? r : -1;
}
int getDist(pii a, pii b) {
	return treX.get(MPX[f(a)], MPX[f(b)]) + treY.get(MPY[f(a)], MPY[f(b)]);
}
int getDist(pii p, int idx) { return getDist(p, QP[idx]); }

void predfs(int i) {
	cnt[i] = 1;
	for(int v : G[i]) if(!cnt[v]) {
		predfs(v);
		cnt[i] += cnt[v];
	}
}
void cent(int &rt) {
	int N = cnt[rt];
	for(int hi, hc;;) {
		hi = hc = -1;
		for(int v : G[rt]) {
			if(N <= cnt[v] || cnt[v] <= hc) continue;
			hc = cnt[v];
			hi = v;
		}
		if(hc*2 <= N) break;
		cnt[rt] = N - hc;
		cnt[hi] = N;
		rt = hi;
	}
}
int centdfs(int i) {
	cent(i);
	for(int v : G[i]) if(cnt[v] < cnt[i]) {
		v = centdfs(v);
		prt[v] = i;
	}
	return i;
}

void initK() {
	{
		vector<int> V;
		for(int i = 1; i <= N; i++) V.eb(MPX[i]);
		sorv(V); univ(V);
		K = sz(V);
		for(int i = 1; i <= N; i++)
			MPK[f(P[i])] = int(lower_bound(allv(V), MPX[f(P[i])]) - V.begin()) + 1;
	}

	for(int i = 1, idx, j; i <= N; i++) {
		idx = MPK[f(P[i])];
		nod[idx].addCell(P[i]);

		j = f(pii(P[i].first + 1, P[i].second));
		if(0 < j) {
			G[idx].eb(MPK[j]);
			G[MPK[j]].eb(idx);
		}
	}

	for(int i = 1; i <= K; i++) {
		sorv(G[i]);
		univ(G[i]);
		nod[i].init();
	}

	predfs(1);
	Krt = centdfs(1);
}

void initTree(int MP[], TRE &tree, int dx) {
	DJF djf;
	for(int i = 1; i <= N; i++) MP[f(P[i])] = i;
	for(int i = 1, j; i <= N; i++) {
		j = f(pii(P[i].first + dx, P[i].second + !dx));
		if(0 < j) djf.uf(i, MP[j]);
	}
	for(int i = 1; i <= N; i++) MP[f(P[i])] = djf.uf(i);
	for(int i = 1, j; i <= N; i++) {
		j = f(pii(P[i].first + !dx, P[i].second + dx));
		if(0 < j) tree.add(djf.uf(i), MP[j]);
	}
	tree.cal();
}

void upd(pii p, int idx) {
	for(int i = MPK[f(p)]; i;) {
		nod[i].addHubo(p, idx);
		i = prt[i];
	}
}
int get(pii p) {
	int r = INF;
	for(int i = MPK[f(p)], t; i;) {
		t = nod[i].get(p);
		if(t < r) r = t;
		i = prt[i];
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> P[i].first >> P[i].second;
		PS[i] = P[i];
	}
	sort(PS+1, PS+N+1);

	initTree(MPX, treX, 0);
	initTree(MPY, treY, 1);
	initK();

	cin >> Q;
	for(int qi = 1, t, x, y; qi <= Q; qi++) {
		cin >> t >> x >> y;
		if(1 == t) {
			QP[qi] = pii(x, y);
			upd(pii(x, y), qi);
		} else {
			t = get(pii(x, y));
			printf("%d\n", INF <= t ? -1 : t);
		}
	}
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 76152 KB Output is correct
2 Correct 69 ms 76280 KB Output is correct
3 Correct 69 ms 76152 KB Output is correct
4 Correct 88 ms 76664 KB Output is correct
5 Correct 93 ms 76784 KB Output is correct
6 Correct 92 ms 76792 KB Output is correct
7 Correct 97 ms 77048 KB Output is correct
8 Correct 96 ms 77196 KB Output is correct
9 Correct 98 ms 77204 KB Output is correct
10 Correct 95 ms 76868 KB Output is correct
11 Correct 99 ms 76920 KB Output is correct
12 Correct 98 ms 76872 KB Output is correct
13 Correct 98 ms 77012 KB Output is correct
14 Correct 96 ms 77048 KB Output is correct
15 Correct 95 ms 77048 KB Output is correct
16 Correct 95 ms 77048 KB Output is correct
17 Correct 93 ms 77048 KB Output is correct
18 Correct 92 ms 76892 KB Output is correct
19 Correct 94 ms 76760 KB Output is correct
20 Correct 98 ms 77176 KB Output is correct
21 Correct 94 ms 77048 KB Output is correct
22 Correct 99 ms 77224 KB Output is correct
23 Correct 94 ms 77176 KB Output is correct
24 Correct 88 ms 77348 KB Output is correct
25 Correct 89 ms 77432 KB Output is correct
26 Correct 83 ms 77176 KB Output is correct
27 Correct 76 ms 76792 KB Output is correct
28 Correct 92 ms 77176 KB Output is correct
29 Correct 91 ms 77304 KB Output is correct
30 Correct 92 ms 77304 KB Output is correct
31 Correct 91 ms 77248 KB Output is correct
32 Correct 95 ms 77048 KB Output is correct
33 Correct 95 ms 76920 KB Output is correct
34 Correct 90 ms 77176 KB Output is correct
35 Correct 94 ms 76996 KB Output is correct
36 Correct 87 ms 77660 KB Output is correct
37 Correct 97 ms 77092 KB Output is correct
38 Correct 93 ms 76964 KB Output is correct
39 Correct 102 ms 76920 KB Output is correct
40 Correct 94 ms 76920 KB Output is correct
41 Correct 91 ms 77176 KB Output is correct
42 Correct 89 ms 77176 KB Output is correct
43 Correct 88 ms 77416 KB Output is correct
44 Correct 92 ms 76920 KB Output is correct
45 Correct 94 ms 76984 KB Output is correct
46 Correct 81 ms 77008 KB Output is correct
47 Correct 98 ms 76796 KB Output is correct
48 Correct 93 ms 76920 KB Output is correct
49 Correct 93 ms 76792 KB Output is correct
50 Correct 92 ms 76812 KB Output is correct
51 Correct 92 ms 76664 KB Output is correct
52 Correct 94 ms 76772 KB Output is correct
53 Correct 99 ms 76896 KB Output is correct
54 Correct 99 ms 76792 KB Output is correct
55 Correct 97 ms 76788 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 76152 KB Output is correct
2 Correct 69 ms 76280 KB Output is correct
3 Correct 69 ms 76152 KB Output is correct
4 Correct 88 ms 76664 KB Output is correct
5 Correct 93 ms 76784 KB Output is correct
6 Correct 92 ms 76792 KB Output is correct
7 Correct 97 ms 77048 KB Output is correct
8 Correct 96 ms 77196 KB Output is correct
9 Correct 98 ms 77204 KB Output is correct
10 Correct 95 ms 76868 KB Output is correct
11 Correct 99 ms 76920 KB Output is correct
12 Correct 98 ms 76872 KB Output is correct
13 Correct 98 ms 77012 KB Output is correct
14 Correct 96 ms 77048 KB Output is correct
15 Correct 95 ms 77048 KB Output is correct
16 Correct 95 ms 77048 KB Output is correct
17 Correct 93 ms 77048 KB Output is correct
18 Correct 92 ms 76892 KB Output is correct
19 Correct 94 ms 76760 KB Output is correct
20 Correct 98 ms 77176 KB Output is correct
21 Correct 94 ms 77048 KB Output is correct
22 Correct 99 ms 77224 KB Output is correct
23 Correct 94 ms 77176 KB Output is correct
24 Correct 88 ms 77348 KB Output is correct
25 Correct 89 ms 77432 KB Output is correct
26 Correct 83 ms 77176 KB Output is correct
27 Correct 76 ms 76792 KB Output is correct
28 Correct 92 ms 77176 KB Output is correct
29 Correct 91 ms 77304 KB Output is correct
30 Correct 92 ms 77304 KB Output is correct
31 Correct 91 ms 77248 KB Output is correct
32 Correct 95 ms 77048 KB Output is correct
33 Correct 95 ms 76920 KB Output is correct
34 Correct 90 ms 77176 KB Output is correct
35 Correct 94 ms 76996 KB Output is correct
36 Correct 87 ms 77660 KB Output is correct
37 Correct 97 ms 77092 KB Output is correct
38 Correct 93 ms 76964 KB Output is correct
39 Correct 102 ms 76920 KB Output is correct
40 Correct 94 ms 76920 KB Output is correct
41 Correct 91 ms 77176 KB Output is correct
42 Correct 89 ms 77176 KB Output is correct
43 Correct 88 ms 77416 KB Output is correct
44 Correct 92 ms 76920 KB Output is correct
45 Correct 94 ms 76984 KB Output is correct
46 Correct 81 ms 77008 KB Output is correct
47 Correct 98 ms 76796 KB Output is correct
48 Correct 93 ms 76920 KB Output is correct
49 Correct 93 ms 76792 KB Output is correct
50 Correct 92 ms 76812 KB Output is correct
51 Correct 92 ms 76664 KB Output is correct
52 Correct 94 ms 76772 KB Output is correct
53 Correct 99 ms 76896 KB Output is correct
54 Correct 99 ms 76792 KB Output is correct
55 Correct 97 ms 76788 KB Output is correct
56 Correct 440 ms 77712 KB Output is correct
57 Correct 431 ms 77688 KB Output is correct
58 Correct 398 ms 77696 KB Output is correct
59 Correct 481 ms 78384 KB Output is correct
60 Correct 608 ms 78216 KB Output is correct
61 Correct 521 ms 78292 KB Output is correct
62 Correct 488 ms 78060 KB Output is correct
63 Correct 473 ms 77948 KB Output is correct
64 Correct 456 ms 78072 KB Output is correct
65 Correct 438 ms 78200 KB Output is correct
66 Correct 432 ms 78040 KB Output is correct
67 Correct 464 ms 78224 KB Output is correct
68 Correct 474 ms 78328 KB Output is correct
69 Correct 513 ms 78240 KB Output is correct
70 Correct 465 ms 77944 KB Output is correct
71 Correct 457 ms 77816 KB Output is correct
72 Correct 479 ms 78084 KB Output is correct
73 Correct 479 ms 78124 KB Output is correct
74 Correct 341 ms 78396 KB Output is correct
75 Correct 226 ms 78204 KB Output is correct
76 Correct 189 ms 77816 KB Output is correct
77 Correct 413 ms 78320 KB Output is correct
78 Correct 388 ms 78348 KB Output is correct
79 Correct 271 ms 78788 KB Output is correct
80 Correct 452 ms 78200 KB Output is correct
81 Correct 462 ms 78108 KB Output is correct
82 Correct 397 ms 78280 KB Output is correct
83 Correct 420 ms 78344 KB Output is correct
84 Correct 321 ms 78468 KB Output is correct
85 Correct 438 ms 78108 KB Output is correct
86 Correct 440 ms 78072 KB Output is correct
87 Correct 175 ms 77944 KB Output is correct
88 Correct 472 ms 77960 KB Output is correct
89 Correct 458 ms 77968 KB Output is correct
90 Correct 468 ms 77788 KB Output is correct
91 Correct 434 ms 77820 KB Output is correct
92 Correct 412 ms 77812 KB Output is correct
93 Correct 428 ms 77944 KB Output is correct
94 Correct 521 ms 78132 KB Output is correct
95 Correct 502 ms 77944 KB Output is correct
96 Correct 495 ms 77928 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 588 ms 177636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1443 ms 190524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 76152 KB Output is correct
2 Correct 69 ms 76280 KB Output is correct
3 Correct 69 ms 76152 KB Output is correct
4 Correct 88 ms 76664 KB Output is correct
5 Correct 93 ms 76784 KB Output is correct
6 Correct 92 ms 76792 KB Output is correct
7 Correct 97 ms 77048 KB Output is correct
8 Correct 96 ms 77196 KB Output is correct
9 Correct 98 ms 77204 KB Output is correct
10 Correct 95 ms 76868 KB Output is correct
11 Correct 99 ms 76920 KB Output is correct
12 Correct 98 ms 76872 KB Output is correct
13 Correct 98 ms 77012 KB Output is correct
14 Correct 96 ms 77048 KB Output is correct
15 Correct 95 ms 77048 KB Output is correct
16 Correct 95 ms 77048 KB Output is correct
17 Correct 93 ms 77048 KB Output is correct
18 Correct 92 ms 76892 KB Output is correct
19 Correct 94 ms 76760 KB Output is correct
20 Correct 98 ms 77176 KB Output is correct
21 Correct 94 ms 77048 KB Output is correct
22 Correct 99 ms 77224 KB Output is correct
23 Correct 94 ms 77176 KB Output is correct
24 Correct 88 ms 77348 KB Output is correct
25 Correct 89 ms 77432 KB Output is correct
26 Correct 83 ms 77176 KB Output is correct
27 Correct 76 ms 76792 KB Output is correct
28 Correct 92 ms 77176 KB Output is correct
29 Correct 91 ms 77304 KB Output is correct
30 Correct 92 ms 77304 KB Output is correct
31 Correct 91 ms 77248 KB Output is correct
32 Correct 95 ms 77048 KB Output is correct
33 Correct 95 ms 76920 KB Output is correct
34 Correct 90 ms 77176 KB Output is correct
35 Correct 94 ms 76996 KB Output is correct
36 Correct 87 ms 77660 KB Output is correct
37 Correct 97 ms 77092 KB Output is correct
38 Correct 93 ms 76964 KB Output is correct
39 Correct 102 ms 76920 KB Output is correct
40 Correct 94 ms 76920 KB Output is correct
41 Correct 91 ms 77176 KB Output is correct
42 Correct 89 ms 77176 KB Output is correct
43 Correct 88 ms 77416 KB Output is correct
44 Correct 92 ms 76920 KB Output is correct
45 Correct 94 ms 76984 KB Output is correct
46 Correct 81 ms 77008 KB Output is correct
47 Correct 98 ms 76796 KB Output is correct
48 Correct 93 ms 76920 KB Output is correct
49 Correct 93 ms 76792 KB Output is correct
50 Correct 92 ms 76812 KB Output is correct
51 Correct 92 ms 76664 KB Output is correct
52 Correct 94 ms 76772 KB Output is correct
53 Correct 99 ms 76896 KB Output is correct
54 Correct 99 ms 76792 KB Output is correct
55 Correct 97 ms 76788 KB Output is correct
56 Correct 440 ms 77712 KB Output is correct
57 Correct 431 ms 77688 KB Output is correct
58 Correct 398 ms 77696 KB Output is correct
59 Correct 481 ms 78384 KB Output is correct
60 Correct 608 ms 78216 KB Output is correct
61 Correct 521 ms 78292 KB Output is correct
62 Correct 488 ms 78060 KB Output is correct
63 Correct 473 ms 77948 KB Output is correct
64 Correct 456 ms 78072 KB Output is correct
65 Correct 438 ms 78200 KB Output is correct
66 Correct 432 ms 78040 KB Output is correct
67 Correct 464 ms 78224 KB Output is correct
68 Correct 474 ms 78328 KB Output is correct
69 Correct 513 ms 78240 KB Output is correct
70 Correct 465 ms 77944 KB Output is correct
71 Correct 457 ms 77816 KB Output is correct
72 Correct 479 ms 78084 KB Output is correct
73 Correct 479 ms 78124 KB Output is correct
74 Correct 341 ms 78396 KB Output is correct
75 Correct 226 ms 78204 KB Output is correct
76 Correct 189 ms 77816 KB Output is correct
77 Correct 413 ms 78320 KB Output is correct
78 Correct 388 ms 78348 KB Output is correct
79 Correct 271 ms 78788 KB Output is correct
80 Correct 452 ms 78200 KB Output is correct
81 Correct 462 ms 78108 KB Output is correct
82 Correct 397 ms 78280 KB Output is correct
83 Correct 420 ms 78344 KB Output is correct
84 Correct 321 ms 78468 KB Output is correct
85 Correct 438 ms 78108 KB Output is correct
86 Correct 440 ms 78072 KB Output is correct
87 Correct 175 ms 77944 KB Output is correct
88 Correct 472 ms 77960 KB Output is correct
89 Correct 458 ms 77968 KB Output is correct
90 Correct 468 ms 77788 KB Output is correct
91 Correct 434 ms 77820 KB Output is correct
92 Correct 412 ms 77812 KB Output is correct
93 Correct 428 ms 77944 KB Output is correct
94 Correct 521 ms 78132 KB Output is correct
95 Correct 502 ms 77944 KB Output is correct
96 Correct 495 ms 77928 KB Output is correct
97 Runtime error 588 ms 177636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
98 Halted 0 ms 0 KB -