Submission #115467

#	Time	Username	Problem	Language	Result	Execution time	Memory
115467		youngyojun	Iqea (innopolis2018_final_C)	C++11	100 / 100	610 ms	46492 KiB

C

#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 || B[j] != i) 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 (stderr)

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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 29 / 29