Submission #115464

# Submission time Handle Problem Language Result Execution time Memory
115464 2019-06-07T15:35:01 Z youngyojun Iqea (innopolis2018_final_C) C++11
15 / 100
2000 ms 72180 KB
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#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 pair<int, int> pii;
void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
static unsigned char str[5500055], *p=str;

const int MAXN = 100005;
const int MAXK = MAXN;
static int _int[MAXN*5], *_intp = _int;
inline int* newint(const unsigned int c) {
	_intp += c;
	return _intp - c;
}

struct BIT {
	int *d, n;

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

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 add(pii p) {
		x = p.first;
		if(p.second < sy) sy = p.second;
		if(ey < p.second) ey = p.second;
	}
	void add(int y, int d) {
		bitu.upd(y-sy, d-y);
		bitd.upd(ey-y, d+y);
	}
	int get(int y) {
		return min(bitu.get(y-sy) + y, bitd.get(ey-y) - y);
	}
} nod[MAXK];

vector<int> T[MAXN], G[MAXK];
int P[17][MAXK];
int C[17][MAXN], CY[17][MAXN];
int D[MAXK], prt[MAXK], cnt[MAXK];

pii A[MAXN];
int B[MAXN];

int N, Q, K;

int getidx(const pii &p) {
	int r = int(lower_bound(A+1, A+N+1, p) - A);
	return r <= N && p == A[r] ? r : 0;
}

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;
			hi = v; hc = cnt[v];
		}
		if(hc*2 <= N) break;
		cnt[rt] = N - hc;
		cnt[hi] = N;
		rt = hi;
	}
}

int makeCD(int i, int d) {
	cent(i);
	D[i] = d; P[d][i] = i;

	queue<int> PQ;
	for(int j = getidx({nod[i].x, nod[i].sy});; j++) {
		if(N < j || A[j].first != nod[i].x) break;
		PQ.push(j);
		C[d][j] = 0;
		CY[d][j] = A[j].second;
	}
	for(int j, c; !PQ.empty(); PQ.pop()) {
		j = PQ.front();
		c = C[d][j] + 1;
		for(int v : T[j]) {
			if(cnt[B[j]] < cnt[B[v]] || C[d][v] <= c) continue;
			PQ.push(v);
			C[d][v] = c;
			CY[d][v] = CY[d][j];
		}
	}

	for(int v : G[i]) if(cnt[v] < cnt[i]) {
		v = makeCD(v, d+1);
		prt[v] = i;
	}
	return i;
}

void makeTree() {
	K = B[1] = 1;
	nod[1].add(A[1]);
	for(int i = 2, j; i <= N; i++) {
		if(A[i-1].first != A[i].first || A[i-1].second != A[i].second-1) K++;
		else fg(T, i-1, i);
		B[i] = K;
		nod[K].add(A[i]);
		j = getidx({A[i].first-1, A[i].second});
		if(j) {
			fg(T, j, i);
			fg(G, B[j], B[i]);
		}
	}
	for(int i = 1; i <= K; i++) {
		nod[i].init();
		sorv(G[i]);
		univ(G[i]);
	}
}

void upd(int i) {
	for(int v = B[i], d = D[v]; v; v = prt[v], d--)
		nod[v].add(CY[d][i], C[d][i]);
}
int get(int i) {
	int r = INF;
	for(int v = B[i], d = D[v], t; v; v = prt[v], d--) {
		t = nod[v].get(CY[d][i]) + C[d][i];
		if(t < r) r = t;
	}
	return N <= r ? -1 : r;
}

int main() {
	fread(str, 1, 5500055, stdin);

	rf(N)
	for(int i = 1; i <= N; i++) { rf(A[i].first) rf(A[i].second) }
	sort(A+1, A+N+1);

	makeTree();
	predfs(1);
	fill(C[0], C[16]+MAXN, INF);
	makeCD(1, 0);

	rf(Q)
	for(int t, x, y; Q--;) {
		rf(t) rf(x) rf(y)
		x = getidx({x, y});
		if(1 == t) upd(x);
		else printf("%d\n", get(x));
	}
	return 0;
}

Compilation message

C.cpp: In function 'int main()':
C.cpp:168:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 5500055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 14 ms 16384 KB Output is correct
2 Correct 14 ms 16512 KB Output is correct
3 Execution timed out 2067 ms 16384 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 14 ms 16384 KB Output is correct
2 Correct 14 ms 16512 KB Output is correct
3 Execution timed out 2067 ms 16384 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 93 ms 25568 KB Output is correct
2 Correct 231 ms 45792 KB Output is correct
3 Correct 199 ms 35804 KB Output is correct
4 Correct 207 ms 35720 KB Output is correct
5 Correct 209 ms 41212 KB Output is correct
6 Correct 217 ms 41060 KB Output is correct
7 Correct 204 ms 30968 KB Output is correct
8 Correct 112 ms 26492 KB Output is correct
9 Correct 79 ms 25044 KB Output is correct
10 Correct 258 ms 30840 KB Output is correct
11 Correct 128 ms 26360 KB Output is correct
12 Correct 80 ms 25044 KB Output is correct
13 Correct 87 ms 24252 KB Output is correct
14 Correct 80 ms 24312 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 750 ms 72180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 14 ms 16384 KB Output is correct
2 Correct 14 ms 16512 KB Output is correct
3 Execution timed out 2067 ms 16384 KB Time limit exceeded
4 Halted 0 ms 0 KB -