Submission #114337

#	Time	Username	Problem	Language	Result	Execution time	Memory
114337		sebinkim	Iqea (innopolis2018_final_C)	C++14	100 / 100	551 ms	49896 KiB

C

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

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

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];
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, vector <cpnt> &X)
{
	vector <cpnt> Y;
	int i, x, y;
	
	for(i=L[p]; i<=R[p]; i++){
		K[H[p] + i - L[p]].push_back(X[i - L[p]]);
	}
	
	for(int &t: V[p]){
		if(t != r && !chk[t]){
			Y.clear();
			for(i=L[t]; i<=R[t]; i++){
				y = min(max(P[H[t] + i - L[t]].second, L[p]), R[p]);
				x = abs(y - P[H[t] + i - L[t]].second) + X[y - L[p]].d + 1;
				Y.emplace_back(c, X[y - L[p]].y, x);
			}
			dfs2(c, t, p, Y);
		}
	}
}

void dnc(int p)
{
	vector <cpnt> X;
	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){
				break;
			}
		}
		if(i == V[p].size()) break;
		else p = V[p][i];
	}
	
	chk[p] = 1;
	
	for(i=L[p]; i<=R[p]; i++){
		X.emplace_back(p, i, 0);
	}
			
	dfs2(p, p, 0, X);
	
	for(int &t: V[p]){
		if(!chk[t]){
			dnc(t);
		}
	}
}

void query1(int p)
{
	int y;
	
	for(cpnt &t: K[p]){
		T1.update(H[t.p] + t.y - L[t.p], t.d - t.y);
		T2.update(H[t.p] + t.y - L[t.p], t.d + t.y);
	}
}

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

int main()
{
	vector <int> X, Y;
	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:109:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<V[p].size(); i++){
            ~^~~~~~~~~~~~
C.cpp:114:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == V[p].size()) break;
      ~~^~~~~~~~~~~~~~
C.cpp: In function 'void query1(int)':
C.cpp:135:6: warning: unused variable 'y' [-Wunused-variable]
  int y;
      ^
C.cpp: In function 'int main()':
C.cpp:183:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, l=0; j<X.size() && l<Y.size(); ){
                 ~^~~~~~~~~
C.cpp:183:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, l=0; j<X.size() && l<Y.size(); ){
                               ~^~~~~~~~~
C.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
C.cpp:165: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:198:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
C.cpp:201: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: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 29 / 29