Submission #50056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50056	2018-06-07T03:29:22 Z	MatheusLealV	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	997 ms	159772 KB

fortune_telling2

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

	sort(v + 1,  v + n + 1, cmp);

	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	21 ms	19320 KB	Output is correct
2	Correct	18 ms	19560 KB	Output is correct
3	Correct	20 ms	19560 KB	Output is correct
4	Correct	20 ms	19644 KB	Output is correct
5	Correct	24 ms	19804 KB	Output is correct
6	Correct	20 ms	19824 KB	Output is correct
7	Correct	21 ms	19912 KB	Output is correct
8	Correct	20 ms	20120 KB	Output is correct
9	Correct	19 ms	20120 KB	Output is correct
10	Correct	19 ms	20120 KB	Output is correct
11	Correct	20 ms	20120 KB	Output is correct
12	Correct	20 ms	20136 KB	Output is correct
13	Correct	21 ms	20168 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	21480 KB	Output is correct
2	Correct	72 ms	23308 KB	Output is correct
3	Correct	106 ms	25424 KB	Output is correct
4	Correct	146 ms	28016 KB	Output is correct
5	Correct	137 ms	29124 KB	Output is correct
6	Correct	137 ms	30280 KB	Output is correct
7	Correct	167 ms	31456 KB	Output is correct
8	Correct	174 ms	32608 KB	Output is correct
9	Correct	105 ms	33232 KB	Output is correct
10	Correct	106 ms	33920 KB	Output is correct
11	Correct	111 ms	34608 KB	Output is correct
12	Correct	95 ms	35340 KB	Output is correct
13	Correct	125 ms	36452 KB	Output is correct
14	Correct	167 ms	37484 KB	Output is correct
15	Correct	158 ms	38764 KB	Output is correct
16	Correct	357 ms	39896 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	178 ms	61700 KB	Output is correct
2	Correct	343 ms	65088 KB	Output is correct
3	Correct	560 ms	69652 KB	Output is correct
4	Correct	930 ms	76604 KB	Output is correct
5	Correct	135 ms	76604 KB	Output is correct
6	Correct	847 ms	84380 KB	Output is correct
7	Correct	865 ms	90196 KB	Output is correct
8	Correct	836 ms	96020 KB	Output is correct
9	Correct	720 ms	101820 KB	Output is correct
10	Correct	743 ms	107640 KB	Output is correct
11	Correct	699 ms	113208 KB	Output is correct
12	Correct	602 ms	119104 KB	Output is correct
13	Correct	665 ms	124704 KB	Output is correct
14	Correct	581 ms	129936 KB	Output is correct
15	Correct	508 ms	135136 KB	Output is correct
16	Correct	521 ms	140120 KB	Output is correct
17	Correct	549 ms	144180 KB	Output is correct
18	Correct	958 ms	148044 KB	Output is correct
19	Correct	911 ms	153864 KB	Output is correct
20	Correct	997 ms	159772 KB	Output is correct