Submission #104026

#	Time	Username	Problem	Language	Result	Execution time	Memory
104026		igba	운세 보기 2 (JOI14_fortune_telling2)	C++17	35 / 100	771 ms	263168 KiB

fortune_telling2

#include <bits/stdc++.h>
 
using namespace std;
const int MAXN = 2 * 100100, MAXK = 2 * 100100, MAXA = 1e9 + 1e2;
int n, k, a[MAXN], b[MAXN];
long long ans = 0;

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

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

int get(no* n, int (*joinFunc)(int, int), int a, int b, int beg = 1, int end = MAXA)
{
	if(!n || b < beg || end < a)
		return 0;
	if(a <= beg && end <= b)
		return getv(n);
	int mid = (beg + end) >> 1;
	return joinFunc(get(n->l, joinFunc, a, b, beg, mid), get(n->r, joinFunc, a, b, mid + 1, end));
}

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

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46: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:48: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:50:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t), pseg[i] = upd(pseg[i - 1], [](int x, int y){ return x + y; }, t), seg = upd(seg, [](int x, int y){ return max(x, y); }, t, i);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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