oj.uz

Submission #50582

# Submission time Handle Problem Language Result Execution time Memory
50582 2018-06-11T16:40:58 Z MatheusLealV Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 582 ms 46464 KB 
#include <bits/stdc++.h>
#define N 200010
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
 
vector<int> tree[4*N];
 
int T[N];
 
ll resp;
 
inline void build(int nod, int a, int b)
{
	if(a == b)
	{
		tree[nod].push_back(T[a]);
 
		return;
	}
	
	int mid = (a+b)/2;
 
	build(2*nod, a, mid);
 
	build(2*nod + 1, mid + 1, b);
 
	tree[nod] = vector<int> (b - a + 1);
 
	merge(tree[2*nod].begin(), tree[2*nod].end(), tree[2*nod + 1].begin(), tree[2*nod + 1].end(), tree[nod].begin());
 
}

inline int conta(int nod, int X, int Y)
{
	if(X > Y) swap(X, Y);

	return upper_bound(tree[nod].begin(), tree[nod].end(), Y) - lower_bound(tree[nod].begin(), tree[nod].end(), X);	
}
 
inline int query_tree(int nod, int a, int b, int i, int j, int X, int Y) 
{
	if(j < a || i > b) return 0;
 
	if(i <= a && j >= b) return conta(nod, X, Y);
	
	int mid = (a + b)/2, cnt = 0;
 
	if( !(j < a || i > mid)) cnt += query_tree(2*nod, a, (a + b)/2, i, j, X, Y);
 
	if( !(j < mid + 1 || i > b)) cnt += query_tree(2*nod + 1, ((a + b)/2) + 1, b, i, j, X, Y);
 
	return cnt;
}
 
struct query
{
	int A, B, pos, tip;
};
 
vector< query > Q;
 
inline bool comp(query L, query R)
{
	if(max(L.A, L.B) != max(R.A, R.B)) return max(L.A, L.B) > max(R.A, R.B);
 
	return L.tip > R.tip;
}
 
int n, m, ans[N], en, st = 200000000;
 
pii inf_en[N];
 
int bsearch(int A, int B, int nod = 1, int a = 1, int b = m)
{
	if(a == b)
	{
		//cout<<tree[nod][0]<<" "<<A<<" "<<B - 1<<" "<<conta(nod, A, B - 1)<<"\n";
		if(!conta(nod, A, B - 1)) return a;

		return ( (a == m) ? -1 : a + 1);
	}
	int cnt = conta(2*nod + 1, A, B - 1), mid = (a + b)/2;

	//cout<<"BSEARCH "<<A<<" "<<B<<" "<<cnt<<"\n";

	if(!cnt) return bsearch(A, B, 2*nod, a, mid);

	else return bsearch(A, B, 2*nod + 1, mid + 1, b);
}

inline int bsearch2(int A, int B)
{
	int ini = 1, fim = m, mid, best = -1;
 
	if(B < A) swap(A, B);
 
	while(fim >= ini)
	{
		mid = (ini + fim)/2;
 
		int Ai = query_tree(1, 1, m, mid, m, A, B - 1);
 
		if(Ai == 0)
		{
			best = mid;
 
			fim = mid - 1;
		}
 
		else ini = mid + 1;
	}
 
	return best;
}
 
pii v[N];
 
inline bool cmp(pii L, pii R)
{
	return max(L.f, L.s) < max(R.f, R.s);
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>m;
 
	for(int i = 1, a, b; i <= n; i++)
	{
		cin>>a>>b;
 
		v[i] = {a, b};
	}
 
	for(int i = 1, x; i <= m; i++) cin>>T[i];
 
	build(1, 1, m);
 
	sort(v + 1,  v + n + 1, cmp);
 
	for(int i = 1; i <= n; i++)
	{
		int iA = v[i].f, iB = v[i].s;

		if(iA > iB) swap(iA, iB);

		int db = bsearch(iA, iB);

		if(db == -1)
		{
			if(v[i].f < v[i].s) ans[i] = v[i].s;
 
			else ans[i] = v[i].f;
		}
 
		else
		{
			int A = v[i].f, B = v[i].s;
 
			if(B < A) swap(A, B);
 
			int Ai = query_tree(1, 1, m, db, m, 0, A - 1);
 
			int inf = (2 + (m - db + 1) - Ai)%2;
 
			if(db <= 1)
			{
				if(inf == 0) ans[i] = v[i].f;
 
				else ans[i] = v[i].s;
			}
 
			else if(inf == 0) // ULTIMO CARA FOI UM TRAÇO
			{
				if(v[i].f < v[i].s) ans[i] = v[i].s;
 
				else ans[i] = v[i].f;
			}
			else
			{
				if(inf == 1) // ULTIMO CARA FOI UM INFINITO
				{
					if (v[i].f < v[i].s)  ans[i] = v[i].f;
 
					else ans[i] = v[i].s;
				}
			}
		}
 
		resp += (ll)ans[i];
	}
 
	cout<<resp<<"\n";
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:139:17: warning: unused variable 'x' [-Wunused-variable]
  for(int i = 1, x; i <= m; i++) cin>>T[i];
                 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 17 ms 19304 KB Output is correct
3 Correct 18 ms 19484 KB Output is correct
4 Correct 19 ms 19484 KB Output is correct
5 Correct 20 ms 19508 KB Output is correct
6 Correct 18 ms 19508 KB Output is correct
7 Correct 18 ms 19532 KB Output is correct
8 Correct 17 ms 19532 KB Output is correct
9 Correct 17 ms 19532 KB Output is correct
10 Correct 18 ms 19532 KB Output is correct
11 Correct 18 ms 19584 KB Output is correct
12 Correct 20 ms 19584 KB Output is correct
13 Correct 18 ms 19584 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 20584 KB Output is correct
2 Correct 54 ms 21756 KB Output is correct
3 Correct 95 ms 23164 KB Output is correct
4 Correct 120 ms 24384 KB Output is correct
5 Correct 114 ms 24572 KB Output is correct
6 Correct 106 ms 24572 KB Output is correct
7 Correct 106 ms 24572 KB Output is correct
8 Correct 96 ms 24572 KB Output is correct
9 Correct 74 ms 24572 KB Output is correct
10 Correct 73 ms 24572 KB Output is correct
11 Correct 68 ms 24572 KB Output is correct
12 Correct 68 ms 24572 KB Output is correct
13 Correct 66 ms 24572 KB Output is correct
14 Correct 82 ms 24572 KB Output is correct
15 Correct 78 ms 24572 KB Output is correct
16 Correct 123 ms 24572 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 44076 KB Output is correct
2 Correct 318 ms 44552 KB Output is correct
3 Correct 347 ms 45344 KB Output is correct
4 Correct 571 ms 46340 KB Output is correct
5 Correct 119 ms 46340 KB Output is correct
6 Correct 582 ms 46340 KB Output is correct
7 Correct 557 ms 46460 KB Output is correct
8 Correct 553 ms 46460 KB Output is correct
9 Correct 521 ms 46460 KB Output is correct
10 Correct 495 ms 46460 KB Output is correct
11 Correct 460 ms 46460 KB Output is correct
12 Correct 407 ms 46460 KB Output is correct
13 Correct 476 ms 46460 KB Output is correct
14 Correct 311 ms 46460 KB Output is correct
15 Correct 289 ms 46460 KB Output is correct
16 Correct 310 ms 46460 KB Output is correct
17 Correct 333 ms 46464 KB Output is correct
18 Correct 342 ms 46464 KB Output is correct
19 Correct 353 ms 46464 KB Output is correct
20 Correct 327 ms 46464 KB Output is correct