Submission #5217

#	Time	Username	Problem	Language	Result	Execution time	Memory
5217		woqja125	trapezoid (balkan11_trapezoid)	C++98	0 / 100	103 ms	9712 KiB

trapezoid

#include<stdio.h>
#include<algorithm>
struct data
{
	int a, b, n, t;
} dat[200001];
struct coor
{
	int *p;
} Y[200001];
struct node
{
	int max;
	int cnt;
} IT[400001];
bool operator<(const coor &A, const coor &B)
{
	return *A.p<*B.p;
}
bool operator<(const data &A, const data &B)
{
	return A.a!=B.a?A.a<B.a:A.t<B.t;
}
int d[100001][2];
node getmax(int f, int r)
{
	node re={ 0, 0 };
	while(f<r)
	{
		if(f%2 == 1)
		{
			if(re.max == IT[f].max) re.cnt += IT[f].cnt;
			else if(re.max < IT[f].max) re = IT[f];
			f++;
		}
		if(r%2 == 0)
		{
			if(re.max == IT[r].max) re.cnt += IT[r].cnt;
			else if(re.max < IT[r].max) re = IT[r];
			r--;
		}
		f/=2;
		r/=2;
	}
	if(f==r)
	{
		if(re.max == IT[r].max) re.cnt += IT[r].cnt;
		else if(re.max < IT[r].max) re = IT[r];
	}
	return re;
}
void init(int x)
{
	while(x/=2)
	{
		if(IT[x*2].max == IT[x*2+1].max)
		{
			IT[x].max = IT[x*2].max;
			IT[x].cnt = IT[x*2].cnt + IT[x*2+1].cnt;
		}
		else if(IT[x*2].max < IT[x*2+1].max)
		{
			IT[x] = IT[x*2+1];
		}
		else
		{
			IT[x] = IT[x*2];
		}
	}
}
int main()
{
	int n, i, a, b, c, D, base;
	node t;
	scanf("%d", &n);
	for(base = 1; base<2*n; base*=2);
	for (i = 1; i <= n; i++)
	{
		scanf("%d%d%d%d", &a, &b, &c, &D);
		dat[i*2-1].a = a;
		dat[i*2].a = b;
		dat[i*2-1].b = c;
		dat[i*2].b = D;
		dat[i*2-1].t = 0;
		dat[i*2].t = 1;
		Y[2*i-1].p = &dat[i*2-1].b;
		Y[2*i].p = &dat[i*2-1].b;
	}
	for(i=1; i<=2*n; i++) *Y[i].p = i;
	std::sort(dat+1, dat+1+2*n);
	IT[base].cnt = 1;
	init(base);
	for(i=1; i<=2*n; i++)
	{
		if(dat[i].t==0)
		{
			t = getmax(base, base+dat[i].b);
			d[dat[i].n][0] = t.max + 1;
			d[dat[i].n][1] = t.cnt;
		}
		else
		{
			IT[base + dat[i].b].max = d[dat[i].n][0];
			IT[base + dat[i].b].cnt = d[dat[i].n][1];
			init(base+dat[i].b);
		}
	}
	t = getmax(base, base+2*n);
	printf("%d %d", t.max, t.cnt);
	return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:75:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
trapezoid.cpp:79:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &D);
                                    ^

• Subtask 1: 0 / 100