oj.uz

Submission #5218

# Submission time Handle Problem Language Result Execution time Memory
5218 2014-02-18T05:23:09 Z woqja125 trapezoid (balkan11_trapezoid) C++
46 / 100
 119 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;
			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;
		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
46.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 Partially correct 0 ms 12056 KB Partially correct
4 Partially correct 0 ms 12056 KB Partially correct
5 Partially correct 0 ms 12056 KB Partially correct
6 Partially correct 0 ms 12056 KB Partially correct
7 Partially correct 3 ms 12056 KB Partially correct
8 Partially correct 3 ms 12056 KB Partially correct
9 Partially correct 9 ms 12056 KB Partially correct
10 Partially correct 19 ms 12056 KB Partially correct
11 Partially correct 26 ms 12056 KB Partially correct
12 Partially correct 49 ms 12056 KB Partially correct
13 Partially correct 76 ms 12056 KB Partially correct
14 Partially correct 89 ms 12056 KB Partially correct
15 Partially correct 99 ms 12056 KB Partially correct
16 Partially correct 106 ms 12056 KB Partially correct
17 Partially correct 113 ms 12056 KB Partially correct
18 Partially correct 96 ms 12056 KB Partially correct
19 Partially correct 106 ms 12056 KB Partially correct
20 Partially correct 119 ms 12056 KB Partially correct