oj.uz

Submission #115098

# Submission time Handle Problem Language Result Execution time Memory
115098 2019-06-05T09:01:46 Z 윤교준(#2865) Iqea (innopolis2018_final_C) C++14
51 / 100
 2000 ms 58180 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 prt[17][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]) {
			prt[0][v] = i;
			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();
*/
		for(int j = 1; j < 17; j++) for(int i = 1; i < MAXN; i++)
			prt[j][i] = prt[j-1][prt[j-1][i]];
	}
	int lca(int a, int b) {
		if(dep[a] > dep[b]) swap(a, b);
		const int dt = dep[b] - dep[a];
		for(int i = 0; i < 17; i++) if(dt & (1<<i)) b = prt[i][b];
		if(a == b) return a;
		for(int i = 17; i--;) if(prt[i][a] != prt[i][b]) {
			a = prt[i][a];
			b = prt[i][b];
		}
		return prt[0][a];
		/*
		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 26 ms 28132 KB Output is correct
2 Correct 26 ms 28160 KB Output is correct
3 Correct 27 ms 28160 KB Output is correct
4 Correct 54 ms 28664 KB Output is correct
5 Correct 58 ms 28836 KB Output is correct
6 Correct 55 ms 28792 KB Output is correct
7 Correct 64 ms 29176 KB Output is correct
8 Correct 62 ms 29180 KB Output is correct
9 Correct 65 ms 29176 KB Output is correct
10 Correct 61 ms 28920 KB Output is correct
11 Correct 62 ms 29048 KB Output is correct
12 Correct 61 ms 29048 KB Output is correct
13 Correct 58 ms 29048 KB Output is correct
14 Correct 63 ms 29048 KB Output is correct
15 Correct 60 ms 29048 KB Output is correct
16 Correct 65 ms 29304 KB Output is correct
17 Correct 63 ms 29048 KB Output is correct
18 Correct 63 ms 28928 KB Output is correct
19 Correct 62 ms 28792 KB Output is correct
20 Correct 64 ms 29048 KB Output is correct
21 Correct 61 ms 29176 KB Output is correct
22 Correct 61 ms 29304 KB Output is correct
23 Correct 59 ms 29176 KB Output is correct
24 Correct 54 ms 29432 KB Output is correct
25 Correct 52 ms 29404 KB Output is correct
26 Correct 42 ms 29176 KB Output is correct
27 Correct 36 ms 28792 KB Output is correct
28 Correct 56 ms 29176 KB Output is correct
29 Correct 56 ms 29304 KB Output is correct
30 Correct 55 ms 29304 KB Output is correct
31 Correct 52 ms 29436 KB Output is correct
32 Correct 58 ms 29048 KB Output is correct
33 Correct 56 ms 28920 KB Output is correct
34 Correct 55 ms 29184 KB Output is correct
35 Correct 60 ms 29180 KB Output is correct
36 Correct 45 ms 29560 KB Output is correct
37 Correct 58 ms 29048 KB Output is correct
38 Correct 55 ms 29048 KB Output is correct
39 Correct 55 ms 28920 KB Output is correct
40 Correct 61 ms 29148 KB Output is correct
41 Correct 55 ms 29244 KB Output is correct
42 Correct 56 ms 29176 KB Output is correct
43 Correct 50 ms 29416 KB Output is correct
44 Correct 58 ms 28920 KB Output is correct
45 Correct 57 ms 28908 KB Output is correct
46 Correct 40 ms 28920 KB Output is correct
47 Correct 63 ms 28920 KB Output is correct
48 Correct 61 ms 28792 KB Output is correct
49 Correct 61 ms 28792 KB Output is correct
50 Correct 63 ms 28792 KB Output is correct
51 Correct 62 ms 28664 KB Output is correct
52 Correct 59 ms 28920 KB Output is correct
53 Correct 67 ms 28920 KB Output is correct
54 Correct 67 ms 28920 KB Output is correct
55 Correct 64 ms 28920 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28132 KB Output is correct
2 Correct 26 ms 28160 KB Output is correct
3 Correct 27 ms 28160 KB Output is correct
4 Correct 54 ms 28664 KB Output is correct
5 Correct 58 ms 28836 KB Output is correct
6 Correct 55 ms 28792 KB Output is correct
7 Correct 64 ms 29176 KB Output is correct
8 Correct 62 ms 29180 KB Output is correct
9 Correct 65 ms 29176 KB Output is correct
10 Correct 61 ms 28920 KB Output is correct
11 Correct 62 ms 29048 KB Output is correct
12 Correct 61 ms 29048 KB Output is correct
13 Correct 58 ms 29048 KB Output is correct
14 Correct 63 ms 29048 KB Output is correct
15 Correct 60 ms 29048 KB Output is correct
16 Correct 65 ms 29304 KB Output is correct
17 Correct 63 ms 29048 KB Output is correct
18 Correct 63 ms 28928 KB Output is correct
19 Correct 62 ms 28792 KB Output is correct
20 Correct 64 ms 29048 KB Output is correct
21 Correct 61 ms 29176 KB Output is correct
22 Correct 61 ms 29304 KB Output is correct
23 Correct 59 ms 29176 KB Output is correct
24 Correct 54 ms 29432 KB Output is correct
25 Correct 52 ms 29404 KB Output is correct
26 Correct 42 ms 29176 KB Output is correct
27 Correct 36 ms 28792 KB Output is correct
28 Correct 56 ms 29176 KB Output is correct
29 Correct 56 ms 29304 KB Output is correct
30 Correct 55 ms 29304 KB Output is correct
31 Correct 52 ms 29436 KB Output is correct
32 Correct 58 ms 29048 KB Output is correct
33 Correct 56 ms 28920 KB Output is correct
34 Correct 55 ms 29184 KB Output is correct
35 Correct 60 ms 29180 KB Output is correct
36 Correct 45 ms 29560 KB Output is correct
37 Correct 58 ms 29048 KB Output is correct
38 Correct 55 ms 29048 KB Output is correct
39 Correct 55 ms 28920 KB Output is correct
40 Correct 61 ms 29148 KB Output is correct
41 Correct 55 ms 29244 KB Output is correct
42 Correct 56 ms 29176 KB Output is correct
43 Correct 50 ms 29416 KB Output is correct
44 Correct 58 ms 28920 KB Output is correct
45 Correct 57 ms 28908 KB Output is correct
46 Correct 40 ms 28920 KB Output is correct
47 Correct 63 ms 28920 KB Output is correct
48 Correct 61 ms 28792 KB Output is correct
49 Correct 61 ms 28792 KB Output is correct
50 Correct 63 ms 28792 KB Output is correct
51 Correct 62 ms 28664 KB Output is correct
52 Correct 59 ms 28920 KB Output is correct
53 Correct 67 ms 28920 KB Output is correct
54 Correct 67 ms 28920 KB Output is correct
55 Correct 64 ms 28920 KB Output is correct
56 Correct 552 ms 29816 KB Output is correct
57 Correct 568 ms 29688 KB Output is correct
58 Correct 556 ms 29652 KB Output is correct
59 Correct 629 ms 30204 KB Output is correct
60 Correct 698 ms 30328 KB Output is correct
61 Correct 662 ms 30200 KB Output is correct
62 Correct 699 ms 30092 KB Output is correct
63 Correct 674 ms 29940 KB Output is correct
64 Correct 631 ms 30084 KB Output is correct
65 Correct 577 ms 30212 KB Output is correct
66 Correct 554 ms 30076 KB Output is correct
67 Correct 637 ms 30348 KB Output is correct
68 Correct 640 ms 30332 KB Output is correct
69 Correct 634 ms 30212 KB Output is correct
70 Correct 629 ms 29944 KB Output is correct
71 Correct 609 ms 29788 KB Output is correct
72 Correct 633 ms 30312 KB Output is correct
73 Correct 622 ms 30200 KB Output is correct
74 Correct 402 ms 30452 KB Output is correct
75 Correct 251 ms 30328 KB Output is correct
76 Correct 196 ms 30012 KB Output is correct
77 Correct 544 ms 30556 KB Output is correct
78 Correct 493 ms 30460 KB Output is correct
79 Correct 300 ms 30768 KB Output is correct
80 Correct 630 ms 30072 KB Output is correct
81 Correct 682 ms 30200 KB Output is correct
82 Correct 505 ms 30300 KB Output is correct
83 Correct 586 ms 30516 KB Output is correct
84 Correct 386 ms 30584 KB Output is correct
85 Correct 603 ms 30108 KB Output is correct
86 Correct 626 ms 30096 KB Output is correct
87 Correct 192 ms 30092 KB Output is correct
88 Correct 710 ms 30004 KB Output is correct
89 Correct 664 ms 29856 KB Output is correct
90 Correct 651 ms 30036 KB Output is correct
91 Correct 627 ms 29808 KB Output is correct
92 Correct 550 ms 29820 KB Output is correct
93 Correct 574 ms 30040 KB Output is correct
94 Correct 699 ms 30176 KB Output is correct
95 Correct 686 ms 30000 KB Output is correct
96 Correct 710 ms 30072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 41664 KB Output is correct
2 Correct 1131 ms 58180 KB Output is correct
3 Correct 1539 ms 47836 KB Output is correct
4 Correct 1692 ms 47620 KB Output is correct
5 Correct 1427 ms 51484 KB Output is correct
6 Correct 1536 ms 52504 KB Output is correct
7 Correct 1464 ms 41064 KB Output is correct
8 Correct 694 ms 42212 KB Output is correct
9 Correct 516 ms 43852 KB Output is correct
10 Correct 1909 ms 40920 KB Output is correct
11 Correct 985 ms 42028 KB Output is correct
12 Correct 607 ms 43684 KB Output is correct
13 Correct 545 ms 41712 KB Output is correct
14 Correct 600 ms 41628 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1948 ms 47776 KB Output is correct
2 Execution timed out 2024 ms 49712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28132 KB Output is correct
2 Correct 26 ms 28160 KB Output is correct
3 Correct 27 ms 28160 KB Output is correct
4 Correct 54 ms 28664 KB Output is correct
5 Correct 58 ms 28836 KB Output is correct
6 Correct 55 ms 28792 KB Output is correct
7 Correct 64 ms 29176 KB Output is correct
8 Correct 62 ms 29180 KB Output is correct
9 Correct 65 ms 29176 KB Output is correct
10 Correct 61 ms 28920 KB Output is correct
11 Correct 62 ms 29048 KB Output is correct
12 Correct 61 ms 29048 KB Output is correct
13 Correct 58 ms 29048 KB Output is correct
14 Correct 63 ms 29048 KB Output is correct
15 Correct 60 ms 29048 KB Output is correct
16 Correct 65 ms 29304 KB Output is correct
17 Correct 63 ms 29048 KB Output is correct
18 Correct 63 ms 28928 KB Output is correct
19 Correct 62 ms 28792 KB Output is correct
20 Correct 64 ms 29048 KB Output is correct
21 Correct 61 ms 29176 KB Output is correct
22 Correct 61 ms 29304 KB Output is correct
23 Correct 59 ms 29176 KB Output is correct
24 Correct 54 ms 29432 KB Output is correct
25 Correct 52 ms 29404 KB Output is correct
26 Correct 42 ms 29176 KB Output is correct
27 Correct 36 ms 28792 KB Output is correct
28 Correct 56 ms 29176 KB Output is correct
29 Correct 56 ms 29304 KB Output is correct
30 Correct 55 ms 29304 KB Output is correct
31 Correct 52 ms 29436 KB Output is correct
32 Correct 58 ms 29048 KB Output is correct
33 Correct 56 ms 28920 KB Output is correct
34 Correct 55 ms 29184 KB Output is correct
35 Correct 60 ms 29180 KB Output is correct
36 Correct 45 ms 29560 KB Output is correct
37 Correct 58 ms 29048 KB Output is correct
38 Correct 55 ms 29048 KB Output is correct
39 Correct 55 ms 28920 KB Output is correct
40 Correct 61 ms 29148 KB Output is correct
41 Correct 55 ms 29244 KB Output is correct
42 Correct 56 ms 29176 KB Output is correct
43 Correct 50 ms 29416 KB Output is correct
44 Correct 58 ms 28920 KB Output is correct
45 Correct 57 ms 28908 KB Output is correct
46 Correct 40 ms 28920 KB Output is correct
47 Correct 63 ms 28920 KB Output is correct
48 Correct 61 ms 28792 KB Output is correct
49 Correct 61 ms 28792 KB Output is correct
50 Correct 63 ms 28792 KB Output is correct
51 Correct 62 ms 28664 KB Output is correct
52 Correct 59 ms 28920 KB Output is correct
53 Correct 67 ms 28920 KB Output is correct
54 Correct 67 ms 28920 KB Output is correct
55 Correct 64 ms 28920 KB Output is correct
56 Correct 552 ms 29816 KB Output is correct
57 Correct 568 ms 29688 KB Output is correct
58 Correct 556 ms 29652 KB Output is correct
59 Correct 629 ms 30204 KB Output is correct
60 Correct 698 ms 30328 KB Output is correct
61 Correct 662 ms 30200 KB Output is correct
62 Correct 699 ms 30092 KB Output is correct
63 Correct 674 ms 29940 KB Output is correct
64 Correct 631 ms 30084 KB Output is correct
65 Correct 577 ms 30212 KB Output is correct
66 Correct 554 ms 30076 KB Output is correct
67 Correct 637 ms 30348 KB Output is correct
68 Correct 640 ms 30332 KB Output is correct
69 Correct 634 ms 30212 KB Output is correct
70 Correct 629 ms 29944 KB Output is correct
71 Correct 609 ms 29788 KB Output is correct
72 Correct 633 ms 30312 KB Output is correct
73 Correct 622 ms 30200 KB Output is correct
74 Correct 402 ms 30452 KB Output is correct
75 Correct 251 ms 30328 KB Output is correct
76 Correct 196 ms 30012 KB Output is correct
77 Correct 544 ms 30556 KB Output is correct
78 Correct 493 ms 30460 KB Output is correct
79 Correct 300 ms 30768 KB Output is correct
80 Correct 630 ms 30072 KB Output is correct
81 Correct 682 ms 30200 KB Output is correct
82 Correct 505 ms 30300 KB Output is correct
83 Correct 586 ms 30516 KB Output is correct
84 Correct 386 ms 30584 KB Output is correct
85 Correct 603 ms 30108 KB Output is correct
86 Correct 626 ms 30096 KB Output is correct
87 Correct 192 ms 30092 KB Output is correct
88 Correct 710 ms 30004 KB Output is correct
89 Correct 664 ms 29856 KB Output is correct
90 Correct 651 ms 30036 KB Output is correct
91 Correct 627 ms 29808 KB Output is correct
92 Correct 550 ms 29820 KB Output is correct
93 Correct 574 ms 30040 KB Output is correct
94 Correct 699 ms 30176 KB Output is correct
95 Correct 686 ms 30000 KB Output is correct
96 Correct 710 ms 30072 KB Output is correct
97 Correct 586 ms 41664 KB Output is correct
98 Correct 1131 ms 58180 KB Output is correct
99 Correct 1539 ms 47836 KB Output is correct
100 Correct 1692 ms 47620 KB Output is correct
101 Correct 1427 ms 51484 KB Output is correct
102 Correct 1536 ms 52504 KB Output is correct
103 Correct 1464 ms 41064 KB Output is correct
104 Correct 694 ms 42212 KB Output is correct
105 Correct 516 ms 43852 KB Output is correct
106 Correct 1909 ms 40920 KB Output is correct
107 Correct 985 ms 42028 KB Output is correct
108 Correct 607 ms 43684 KB Output is correct
109 Correct 545 ms 41712 KB Output is correct
110 Correct 600 ms 41628 KB Output is correct
111 Correct 1948 ms 47776 KB Output is correct
112 Execution timed out 2024 ms 49712 KB Time limit exceeded
113 Halted 0 ms 0 KB -