# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
5218 | woqja125 | 사다리꼴 (balkan11_trapezoid) | C++98 | 119 ms | 12056 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |