oj.uz

답안 #50056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50056 2018-06-07T03:29:22 Z MatheusLealV 운세 보기 2 (JOI14_fortune_telling2) C++17
100 / 100
 997 ms 159772 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);

	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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