oj.uz

Submission #114261

# Submission time Handle Problem Language Result Execution time Memory
114261 2019-05-31T15:55:20 Z sebinkim Iqea (innopolis2018_final_C) C++14
15 / 100
 2000 ms 166472 KB 
#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(L[t], s), e), max(min(R[t], e), s));
		}
	}
}

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]);
	
	for(int &t: V[p]){
		if(!chk[t]){
			dnc(t);
		}
	}
}

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

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:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, l=0; j<X.size() && l<Y.size(); ){
                 ~^~~~~~~~~
C.cpp:169:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, l=0; j<X.size() && l<Y.size(); ){
                               ~^~~~~~~~~
C.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
C.cpp:151: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:184:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
C.cpp:187: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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Incorrect 8 ms 7168 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Incorrect 8 ms 7168 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8684 KB Output is correct
2 Correct 312 ms 55132 KB Output is correct
3 Correct 218 ms 21092 KB Output is correct
4 Correct 224 ms 23500 KB Output is correct
5 Correct 279 ms 36124 KB Output is correct
6 Correct 288 ms 36156 KB Output is correct
7 Correct 188 ms 13476 KB Output is correct
8 Correct 108 ms 11536 KB Output is correct
9 Correct 100 ms 11256 KB Output is correct
10 Correct 227 ms 13296 KB Output is correct
11 Correct 154 ms 11372 KB Output is correct
12 Correct 145 ms 11132 KB Output is correct
13 Correct 99 ms 10604 KB Output is correct
14 Correct 109 ms 10488 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 166472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Incorrect 8 ms 7168 KB Output isn't correct
4 Halted 0 ms 0 KB -