oj.uz

Submission #50057

# Submission time Handle Problem Language Result Execution time Memory
50057 2018-06-07T03:30:57 Z MatheusLealV Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1381 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 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 upper_bound(tree[nod].begin(), tree[nod].end(), Y) - lower_bound(tree[nod].begin(), tree[nod].end(), X);
	
	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];

inline int bsearch(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];

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);

	for(int i = 1; i <= n; i++)
	{
		int db = bsearch(v[i].f, v[i].s);

		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:114: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 19 ms 19192 KB Output is correct
2 Correct 18 ms 19300 KB Output is correct
3 Correct 20 ms 19452 KB Output is correct
4 Correct 19 ms 19452 KB Output is correct
5 Correct 18 ms 19452 KB Output is correct
6 Correct 18 ms 19488 KB Output is correct
7 Correct 20 ms 19488 KB Output is correct
8 Correct 21 ms 19488 KB Output is correct
9 Correct 22 ms 19488 KB Output is correct
10 Correct 21 ms 19504 KB Output is correct
11 Correct 18 ms 19504 KB Output is correct
12 Correct 24 ms 19504 KB Output is correct
13 Correct 21 ms 19504 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20588 KB Output is correct
2 Correct 88 ms 21780 KB Output is correct
3 Correct 118 ms 23148 KB Output is correct
4 Correct 215 ms 24556 KB Output is correct
5 Correct 166 ms 24556 KB Output is correct
6 Correct 158 ms 24556 KB Output is correct
7 Correct 203 ms 24556 KB Output is correct
8 Correct 173 ms 24556 KB Output is correct
9 Correct 110 ms 24556 KB Output is correct
10 Correct 96 ms 24556 KB Output is correct
11 Correct 102 ms 24556 KB Output is correct
12 Correct 111 ms 24556 KB Output is correct
13 Correct 199 ms 24556 KB Output is correct
14 Correct 307 ms 24572 KB Output is correct
15 Correct 169 ms 24572 KB Output is correct
16 Correct 490 ms 24644 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 44060 KB Output is correct
2 Correct 390 ms 44668 KB Output is correct
3 Correct 620 ms 45180 KB Output is correct
4 Correct 1115 ms 46332 KB Output is correct
5 Correct 150 ms 46332 KB Output is correct
6 Correct 1103 ms 46404 KB Output is correct
7 Correct 1004 ms 46404 KB Output is correct
8 Correct 1117 ms 46428 KB Output is correct
9 Correct 1081 ms 46428 KB Output is correct
10 Correct 1178 ms 46428 KB Output is correct
11 Correct 815 ms 46460 KB Output is correct
12 Correct 1020 ms 46460 KB Output is correct
13 Correct 1133 ms 46464 KB Output is correct
14 Correct 563 ms 46464 KB Output is correct
15 Correct 542 ms 46464 KB Output is correct
16 Correct 571 ms 46464 KB Output is correct
17 Correct 653 ms 46464 KB Output is correct
18 Correct 763 ms 46464 KB Output is correct
19 Correct 1381 ms 46464 KB Output is correct
20 Correct 1090 ms 46464 KB Output is correct