oj.uz

답안 #5219

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5219 2014-02-18T05:24:34 Z woqja125 사다리꼴 (balkan11_trapezoid) C++
100 / 100
 113 ms 12056 KB 
#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[700001];
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;
}
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)%=30013;
			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)%=30013;
			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)%=30013;
		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)%30013;
		}
		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;
		dat[i*2-1].n = dat[i*2].n = i;
		Y[2*i-1].p = &dat[i*2-1].b;
		Y[2*i].p = &dat[i*2].b;
	}
	std::sort(Y+1, Y+1+2*n);
	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

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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12056 KB Output is correct
2 Correct 0 ms 12056 KB Output is correct
3 Correct 0 ms 12056 KB Output is correct
4 Correct 0 ms 12056 KB Output is correct
5 Correct 0 ms 12056 KB Output is correct
6 Correct 3 ms 12056 KB Output is correct
7 Correct 3 ms 12056 KB Output is correct
8 Correct 3 ms 12056 KB Output is correct
9 Correct 9 ms 12056 KB Output is correct
10 Correct 16 ms 12056 KB Output is correct
11 Correct 26 ms 12056 KB Output is correct
12 Correct 56 ms 12056 KB Output is correct
13 Correct 76 ms 12056 KB Output is correct
14 Correct 86 ms 12056 KB Output is correct
15 Correct 96 ms 12056 KB Output is correct
16 Correct 106 ms 12056 KB Output is correct
17 Correct 103 ms 12056 KB Output is correct
18 Correct 76 ms 12056 KB Output is correct
19 Correct 96 ms 12056 KB Output is correct
20 Correct 113 ms 12056 KB Output is correct