Submission #240273

#	Time	Username	Problem	Language	Result	Execution time	Memory
240273		frodakcin	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	680 ms	58904 KiB

fortune_telling2

#include <cstdio>
#include <cstring>
#define NDEBUG
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>

using ll = long long;
const int MN = 2e5+10, MK = 2e5+10, MV = MN*2+MK, MX = 1.5e7;//MX = 1.5e7

int s[MX], c[MX][2], X=1, v[MV], V, a[MN], b[MN], t[MK], N, K, n[MV], r[MN];
struct evt{public:int v, id;bool operator < (evt o)const{return v>o.v;}};//reversed sort
std::vector<evt> q;
ll f;

int upd(int n, int l, int r, int q, int v)
{
	++X;
	assert(X<MX);
	if(n)
	{
		memcpy(c[X], c[n], 8);
		s[X]=s[n];
	}
	n=X;
	s[n]+=v;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(q<m) c[n][0]=upd(c[n][0], l, m, q, v);
		else c[n][1]=upd(c[n][1], m, r, q, v);
		assert(s[n] == s[c[n][0]] + s[c[n][1]]);
	}
	return n;
}
int diff(int n, int u, int l, int r)
{
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(s[c[n][1]] != s[c[u][1]]) return diff(c[n][1], c[u][1], m, r);
		else return diff(c[n][0], c[u][0], l, m);
	}
	else
		return l;
}
int qry(int n, int l, int r, int ql, int qr)
{
	if(!n) return 0;
	if(ql <= l&&r <= qr) return s[n];
	else
	{
		int m=l+(r-l)/2, f=0;
		if(ql<m) f+=qry(c[n][0], l, m, ql, qr);
		if(m<qr) f+=qry(c[n][1], m, r, ql, qr);
		return f;
	}
}
int main()
{
	scanf("%d%d", &N, &K);
	for(int i=0;i<N;++i)
	{
		scanf("%d", a+i), v[V++]=a[i];
		scanf("%d", b+i), v[V++]=b[i];
	}
	for(int i=0;i<K;++i) scanf("%d", t+i), v[V++]=t[i];
	std::sort(v, v+V);
	V = std::unique(v, v+V)-v;
	//for(int i=0;i<V;++i) printf("%d%c", v[i], " \n"[i+1==V]);
	for(int i=0;i<K;++i)
		t[i]=std::lower_bound(v, v+V, t[i])-v, q.push_back({t[i], i});
	std::sort(q.begin(), q.end());
	r[V]=1;
	for(int i=V-1,j=0;i>=0;--i)
	{
		r[i]=r[i+1];
		for(;j<K&&q[j].v==i;++j)//greater or equ
			r[i] = upd(r[i], 0, K, q[j].id, 1);
		//printf("NUM: %d: %d\n", v[i], s[r[i]]);
	}
	for(int i=0;i<N;++i)
	{
		a[i]=std::lower_bound(v, v+V, a[i])-v;
		b[i]=std::lower_bound(v, v+V, b[i])-v;
		//printf("TESTALL(%d,%d): %d %d\n", v[a[i]], v[b[i]], s[r[a[i]]], s[r[b[i]]]);
		if(s[r[a[i]]] == s[r[b[i]]])
			if(s[r[a[i]]]&1)
				f+=v[b[i]];
			else
				f+=v[a[i]];
		else
		{
			assert(a[i]!=b[i]);
			int t=diff(r[a[i]], r[b[i]], 0, K), u=t+1<K?qry(r[a[i]], 0, K, t+1, K):0;//for finding u, result should be same for r[a[i]] and r[b[i]]
			//greater one is selected, then perform u queries
			//printf("%d: %d %d\n", i, t, u);
			if(b[i]>a[i])++u;
			if(u&1)
				f+=v[b[i]];
			else
				f+=v[a[i]];
		}
	}
	printf("%lld\n", f);
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:62: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:65:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i), v[V++]=a[i];
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:66:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b+i), v[V++]=b[i];
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:68:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<K;++i) scanf("%d", t+i), v[V++]=t[i];
                       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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