oj.uz

Submission #5219

# Submission time Handle Problem Language Result Execution time Memory
5219 2014-02-18T05:24:34 Z woqja125 trapezoid (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

# Verdict Execution time Memory 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