oj.uz

Submission #5217

# Submission time Handle Problem Language Result Execution time Memory
5217 2014-02-18T05:12:20 Z woqja125 trapezoid (balkan11_trapezoid) C++
0 / 100
 103 ms 9712 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[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

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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9712 KB Output isn't correct
2 Incorrect 0 ms 9712 KB Output isn't correct
3 Incorrect 0 ms 9712 KB Output isn't correct
4 Incorrect 0 ms 9712 KB Output isn't correct
5 Incorrect 0 ms 9712 KB Output isn't correct
6 Incorrect 3 ms 9712 KB Output isn't correct
7 Incorrect 3 ms 9712 KB Output isn't correct
8 Incorrect 3 ms 9712 KB Output isn't correct
9 Incorrect 6 ms 9712 KB Output isn't correct
10 Incorrect 13 ms 9712 KB Output isn't correct
11 Incorrect 23 ms 9712 KB Output isn't correct
12 Incorrect 49 ms 9712 KB Output isn't correct
13 Incorrect 59 ms 9712 KB Output isn't correct
14 Runtime error 56 ms 9712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 73 ms 9712 KB Output isn't correct
16 Incorrect 96 ms 9712 KB Output isn't correct
17 Runtime error 66 ms 9712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Incorrect 79 ms 9712 KB Output isn't correct
19 Runtime error 69 ms 9712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 103 ms 9712 KB Output isn't correct