oj.uz

Submission #50583

# Submission time Handle Problem Language Result Execution time Memory
50583 2018-06-11T16:41:36 Z MatheusLealV Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 792 ms 46588 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)
	{
		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;

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

	else return bsearch(A, B, 2*nod + 1, mid + 1, b);
}
 
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:111: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 18 ms 19156 KB Output is correct
2 Correct 17 ms 19312 KB Output is correct
3 Correct 18 ms 19464 KB Output is correct
4 Correct 19 ms 19584 KB Output is correct
5 Correct 18 ms 19584 KB Output is correct
6 Correct 22 ms 19584 KB Output is correct
7 Correct 18 ms 19584 KB Output is correct
8 Correct 18 ms 19584 KB Output is correct
9 Correct 17 ms 19584 KB Output is correct
10 Correct 18 ms 19584 KB Output is correct
11 Correct 18 ms 19584 KB Output is correct
12 Correct 17 ms 19584 KB Output is correct
13 Correct 20 ms 19584 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20604 KB Output is correct
2 Correct 60 ms 21828 KB Output is correct
3 Correct 85 ms 23180 KB Output is correct
4 Correct 112 ms 24516 KB Output is correct
5 Correct 113 ms 24516 KB Output is correct
6 Correct 118 ms 24516 KB Output is correct
7 Correct 117 ms 24516 KB Output is correct
8 Correct 94 ms 24516 KB Output is correct
9 Correct 63 ms 24516 KB Output is correct
10 Correct 65 ms 24516 KB Output is correct
11 Correct 65 ms 24516 KB Output is correct
12 Correct 61 ms 24516 KB Output is correct
13 Correct 95 ms 24516 KB Output is correct
14 Correct 134 ms 24516 KB Output is correct
15 Correct 91 ms 24516 KB Output is correct
16 Correct 150 ms 24572 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 44036 KB Output is correct
2 Correct 284 ms 44540 KB Output is correct
3 Correct 458 ms 45176 KB Output is correct
4 Correct 730 ms 46460 KB Output is correct
5 Correct 148 ms 46460 KB Output is correct
6 Correct 684 ms 46460 KB Output is correct
7 Correct 720 ms 46460 KB Output is correct
8 Correct 739 ms 46460 KB Output is correct
9 Correct 692 ms 46588 KB Output is correct
10 Correct 792 ms 46588 KB Output is correct
11 Correct 538 ms 46588 KB Output is correct
12 Correct 723 ms 46588 KB Output is correct
13 Correct 760 ms 46588 KB Output is correct
14 Correct 354 ms 46588 KB Output is correct
15 Correct 324 ms 46588 KB Output is correct
16 Correct 326 ms 46588 KB Output is correct
17 Correct 310 ms 46588 KB Output is correct
18 Correct 363 ms 46588 KB Output is correct
19 Correct 656 ms 46588 KB Output is correct
20 Correct 474 ms 46588 KB Output is correct