제출 #50056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50056		MatheusLealV	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	997 ms	159772 KiB

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";
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65