Submission #13547

#	Time	Username	Problem	Language	Result	Execution time	Memory
13547		woqja125	Fortune Telling 2 (JOI14_fortune_telling2)	C++98	0 / 100	112 ms	14632 KiB

fortune_telling2

#include<stdio.h>
#include<vector>
#include<algorithm>
void set2(int x, int v);
int getsum2(int f, int r);
void set1(int x, int v);
int getmax1(int f, int r);
int max(int a, int b){return a>b?a:b;}
int min(int a, int b){return a<b?a:b;}
std::vector<int> X;
int a[200001];
int b[200001];
int q[200001];
int base;
struct dat
{
	int i, loc, o;
	bool operator<(const dat &A) const{return loc<A.loc;}
} D[200001];
int main()
{
	int n, k;
	int i, j;
	scanf("%d%d", &n, &k);
	for(i=1; i<=n; i++)
	{
		scanf("%d%d", a+i, b+i);
		if(a[i] > b[i]){int t = a[i]; a[i] = b[i]; b[i] = t; D[i].o = 1;}
		X.push_back(a[i]);
		X.push_back(b[i]);
	}
	std::sort(X.begin(), X.end());
	X.erase(std::unique(X.begin(), X.end()), X.end());
	for(base=1; base<=X.size()+1; base*=2);
	for(i=1; i<=n; i++)
	{
		a[i] = std::lower_bound(X.begin(), X.end(), a[i]) - X.begin() + 1;
		b[i] = std::lower_bound(X.begin(), X.end(), b[i]) - X.begin() + 1;
	}
	for(i=1; i<=k; i++)
	{
		scanf("%d", q+i);
		q[i] = std::lower_bound(X.begin(), X.end(), q[i]) - X.begin() + 1;
		set1(q[i], i);
		set2(q[i], 1);
	}
	for(i=1; i<=n; i++)
	{
		int l = getmax1(a[i], b[i]-1);
		D[i].i = i;
		D[i].loc = l;
		if(l!=0) D[i].o = 1;
	}
	std::sort(D+1, D+1+n);
	j=1;
	long long sum = 0;
	for(i=1; i<=n; i++)
	{
		for(; j<=D[i].loc; j++)set2(q[j], -1);
		if((D[i].o + getsum2(b[D[i].i], X.size()))&1) sum += X[b[D[i].i]-1];
		else sum += X[a[D[i].i]-1];
	}
	printf("%lld", sum);
	return 0;
}


int IT1[550000*2];
void set1(int x, int v){for(IT1[x+=base] = v; x/=2;)IT1[x]=max(IT1[2*x], IT1[2*x+1]);}
int getmax1(int f, int r)
{
	f+=base; r+=base;
	int re = 0;
	while(f<r)
	{
		if(f%2==1) re = max(re, IT1[f++]);
		if(r%2==0) re = max(re, IT1[r--]);
		f/=2; r/=2;
	}
	if(f==r) re = max(re, IT1[f]);
	return re;
}

int IT2[550000*2];
void set2(int x, int v){for(IT2[x+=base] += v; x/=2;)IT2[x]=IT2[2*x]+IT2[2*x+1];}
int getsum2(int f, int r)
{
	f+=base; r+=base;
	int re = 0;
	while(f<r)
	{
		if(f%2==1) re += IT2[f++];
		if(r%2==0) re += IT2[r--];
		f/=2; r/=2;
	}
	if(f==r) re += IT2[f];
	return re;
}

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