Submission #114259

#	Time	Username	Problem	Language	Result	Execution time	Memory
114259		sebinkim	Iqea (innopolis2018_final_C)	C++14	0 / 100	143 ms	15632 KiB

C

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

struct cpnt{
	int p, d, l, r;
	cpnt() {}
	cpnt(int p, int d, int l, int r) : p(p), d(d), l(l), r(r) {}
};

struct minseg{
	int T[303030];
	int sz = 1 << 17;
	
	minseg()
	{
		int i;
		
		for(i=0; i<sz+sz; i++){
			T[i] = 1e9;
		}
	}
	
	void update(int p, int v)
	{
		p += sz;
		T[p] = min(T[p], v);
		
		for(p>>=1; p; p>>=1){
			T[p] = min(T[p << 1], T[p << 1 | 1]);
		}
	}
	
	int get_min(int l, int r)
	{
		int ret = 1e9;
		
		l += sz; r += sz;
		
		for(; l<r; ){
			if(l & 1) ret = min(ret, T[l]);
			if(~r & 1) ret = min(ret, T[r]);
			l = l + 1 >> 1;
			r = r - 1 >> 1;
		}
		
		if(l == r){
			ret = min(ret, T[l]);
		}
		
		return ret;
	}
};

vector <pii> P;
vector <int> V[101010], X, Y;
vector <cpnt> K[101010];
minseg T1, T2;
int L[101010], R[101010], H[101010];
int S[101010], D[101010];
bool chk[101010];
int n, k;

int dfs1(int p, int r)
{
	S[p] = 1;
	
	for(int &t: V[p]){
		if(t != r && !chk[t]){
			S[p] += dfs1(t, p);
		}
	}
	
	return S[p];
}

void dfs2(int c, int p, int r, int d, int s, int e)
{
	K[p].emplace_back(c, d, s, e);
	
	for(int &t: V[p]){
		if(t != r && !chk[t]){
			dfs2(c, t, p, d + 1, min(max(s, L[t]), R[t]), max(min(e, R[t]), L[t]));
		}
	}
}

void dnc(int p)
{
	int i, s;
	
	s = dfs1(p, 0);
	
	for(; ; ){
		for(i=0; i<V[p].size(); i++){
			if(S[V[p][i]] < S[p] && S[V[p][i]] * 2 >= s){
				p = V[p][i]; break;
			}
		}
		if(i == V[p].size()) break;
	}
	
	chk[p] = 1;
	
	dfs2(p, p, 0, 0, L[p], R[p]);
}

void query1(int p)
{
	int y;
	
	for(cpnt &t: K[D[p]]){
		y = min(max(P[p].second, t.l), t.r);
		T1.update(H[t.p] + y - L[t.p], (t.d + abs(P[p].second - y)) - (y - L[t.p]));
		T2.update(H[t.p] + y - L[t.p], (t.d + abs(P[p].second - y)) + (y - L[t.p]));
	}
}

int query2(int p)
{
	int y, ret;
	
	ret = 1e9;
	
	for(cpnt &t: K[D[p]]){
		y = min(max(P[p].second, t.l), t.r);
		ret = min(ret, t.d + abs(P[p].second - y) + 
			T1.get_min(H[t.p], H[t.p] + y - L[t.p]) + (y - L[t.p]));
		ret = min(ret, t.d + abs(P[p].second - y) +
			T2.get_min(H[t.p] + y - L[t.p], H[t.p] + R[t.p] - L[t.p]) - (y - L[t.p]));
	}
	
	return ret < 1e8? ret : -1;
}

int main()
{
	int q, i, j, l, x, y, t;
	
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d%d", &x, &y);
		P.emplace_back(x, y);
	}
	
	sort(P.begin(), P.end());
	
	for(i=0; i<n; ){
		for(j=i; j<n && P[i].first == P[j].first; j=l){
			k ++;
			for(l=j; l<n && P[j].first == P[l].first && P[j].second == P[l].second - l + j; l++){
				D[l] = k;
			}
			L[k] = P[j].second; R[k] = P[l - 1].second; H[k] = j;
			X.push_back(k);
		}
		
		i = j;
		
		for(j=0, l=0; j<X.size() && l<Y.size(); ){
			if(max(L[X[j]], L[Y[l]]) <= min(R[X[j]], R[Y[l]])){
				V[X[j]].push_back(Y[l]);
				V[Y[l]].push_back(X[j]);
			}
			
			if(R[X[j]] < R[Y[l]]) j ++;
			else l ++;
		}
		
		swap(X, Y); X.clear();
	}
	
	dnc(1);
	
	scanf("%d", &q);
	
	for(; q--; ){
		scanf("%d%d%d", &t, &x, &y);
		i = lower_bound(P.begin(), P.end(), pii(x, y)) - P.begin();
		if(t == 1) query1(i);
		else printf("%d\n", query2(i));
	}
	
	return 0;
}

Compilation message (stderr)

C.cpp: In member function 'int minseg::get_min(int, int)':
C.cpp:45:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    l = l + 1 >> 1;
        ~~^~~
C.cpp:46:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    r = r - 1 >> 1;
        ~~^~~
C.cpp: In function 'void dnc(int)':
C.cpp:97:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<V[p].size(); i++){
            ~^~~~~~~~~~~~
C.cpp:102:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == V[p].size()) break;
      ~~^~~~~~~~~~~~~~
C.cpp: In function 'int main()':
C.cpp:163:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, l=0; j<X.size() && l<Y.size(); ){
                 ~^~~~~~~~~
C.cpp:163:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, l=0; j<X.size() && l<Y.size(); ){
                               ~^~~~~~~~~
C.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
C.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
C.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
C.cpp:181:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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