제출 #103988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103988		igba	운세 보기 2 (JOI14_fortune_telling2)	C++17	35 / 100	3116 ms	203896 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2 * 100100, MAXK = 2 * 100100, MAXA = 1e9 + 1e4;
int n, k, a[MAXN], b[MAXN], t[MAXK];
long long ans = 0;

struct no
{
	int cnt;
	no *l, *r;
	no(int cnt = 0) : cnt(cnt), l(nullptr), r(nullptr)
	{}
};
inline int getcnt(no *n) { return (n ? n->cnt : 0); }

no* upd(no* n, int pos, int val = 1, int beg = 1, int end = MAXA)
{
	if(beg == end)
		return new no(getcnt(n) + val);
	no* ans = (n ? new no(*n) : new no());
	int mid = (beg + end) >> 1;
	if(pos <= mid)
		ans->l = upd(ans->l, pos, val, beg, mid);
	else
		ans->r = upd(ans->r, pos, val, mid + 1, end);
	ans->cnt = getcnt(ans->l) + getcnt(ans->r);
	return ans;
}

int get(no* n, int pos, int beg = 1, int end = MAXA)
{
	if(!n)
		return 0;
	int mid = (beg + end) >> 1;
	if(pos <= mid)
		return get(n->l, pos, beg, mid) + getcnt(n->r);
	return get(n->r, pos, mid + 1, end);
}

no* pseg[MAXK];

int bs(int x, int y)
{
	if(x < y)
		swap(x, y);
	int beg = 0, end = k, mid, p, q;
	while(beg < end)
	{
		mid = (beg + end + 1) >> 1;
		p = get(pseg[end], y - 1) - get(pseg[mid - 1], y - 1);
		q = get(pseg[end], x - 1) - get(pseg[mid - 1], x - 1);
		if(p - q > 0)
			beg = mid;			
		else
			end = mid - 1;
	}
	return beg;
}

int main()
{
	pseg[0] = nullptr;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d %d", &a[i], &b[i]);
	for(int i = 1; i <= k; ++i)
		scanf("%d", &t[i]), pseg[i] = upd(pseg[i - 1], t[i]);
	for(int i = 1, swaps, j; i <= n; ++i)
	{
		/*for(j = k, swaps = 0; j >= 1; --j)
			if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
				break;*/
		j = bs(a[i], b[i]), swaps = 0;
		if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
			swaps += (a[i] < b[i]);
		swaps += get(pseg[k], max(a[i], b[i]) - 1) - get(pseg[j], max(a[i], b[i]) - 1);
		ans += (swaps % 2 ? b[i] : a[i]);
	}
	printf("%lld\n", ans);
}

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

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t[i]), pseg[i] = upd(pseg[i - 1], t[i]);
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65