oj.uz

Submission #12169

# Submission time Handle Problem Language Result Execution time Memory
12169 2014-12-21T13:50:30 Z dohyun0324 trapezoid (balkan11_trapezoid) C++
46 / 100
 229 ms 12840 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int dap,sum,t=1,w,n,tree[800010],cnt[800010],d[200010],d2[200010];
struct data
{
    int x1,y1,x2,y2;
    bool operator<(const data&r)const{
        return x1<r.x1;
    }
}a[100010];
struct data2
{
    int y,p;
    bool operator<(const data2&r)const{
        return y<r.y;
    }
}b[100010];
struct data3
{
    int x,p;
    bool operator<(const data3&r)const{
        return x<r.x;
    }
}arr[200010];
void ins(int x,int gap,int i)
{
    int p=x+t-1;
    while(p>0)
    {
        if(tree[p]==gap) cnt[p]+=d2[i];
        if(tree[p]<gap) cnt[p]=d2[i];
        tree[p]=max(tree[p],gap);
        p/=2;
    }
}
int query(int a,int b,int x,int y,int k)
{
    if(a<=x && y<=b) return tree[k];
    if(a>y || x>b) return 0;
    return max(query(a,b,x,(x+y)/2,k*2),query(a,b,(x+y)/2+1,y,k*2+1));
}
int query2(int a,int b,int x,int y,int k)
{
    int s1,s2;
    if(a<=x && y<=b) return cnt[k];
    if(a>y || x>b) return 0;
    s1=query(a,b,x,(x+y)/2,k*2); s2=query(a,b,(x+y)/2+1,y,k*2+1);
    if(s1==s2) return query2(a,b,x,(x+y)/2,k*2)+query2(a,b,(x+y)/2+1,y,k*2+1);
    else if(s1>s2) return query2(a,b,x,(x+y)/2,k*2);
    else return query2(a,b,(x+y)/2+1,y,k*2+1);
}
int main()
{
    int i,j,p=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d %d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
        w++; arr[w].x=a[i].x2; arr[w].p=i*2; w++; arr[w].x=a[i].y2; arr[w].p=i*2+1;
    }
    sort(arr+1,arr+w+1);
    for(i=1;i<=w;i++)
    {
        if(arr[i].p%2==0) a[arr[i].p/2].x2=i;
        else a[arr[i].p/2].y2=i;
    }
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++) b[i].y=a[i].y1, b[i].p=i;
    for(i=1;;i++){if(t>=w) break; t*=2;}
    sort(b+1,b+n+1);
    for(i=1;i<=n;i++)
    {
        for(j=p;j<=n;j++)
        {
            if(a[i].x1<b[j].y) break;
            ins(a[b[j].p].y2,d[b[j].p],b[j].p);
        }
        p=j;
        d[i]=query(1,a[i].x2-1,1,t,1)+1;
        d2[i]=query2(1,a[i].x2-1,1,t,1);
        if(d[i]==1) d2[i]=1;
    }
    for(i=1;i<=n;i++)
    {
        if(dap==d[i]) sum+=d2[i];
        if(dap<d[i])
        {
            dap=d[i];
            sum=d2[i];
        }
    }
    printf("%d %d",dap,sum);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:56:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:59:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
                                                                 ^

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12840 KB Output is correct
2 Correct 0 ms 12840 KB Output is correct
3 Partially correct 0 ms 12840 KB Partially correct
4 Partially correct 0 ms 12840 KB Partially correct
5 Partially correct 3 ms 12840 KB Partially correct
6 Partially correct 3 ms 12840 KB Partially correct
7 Partially correct 6 ms 12840 KB Partially correct
8 Partially correct 9 ms 12840 KB Partially correct
9 Partially correct 19 ms 12840 KB Partially correct
10 Partially correct 36 ms 12840 KB Partially correct
11 Partially correct 43 ms 12840 KB Partially correct
12 Partially correct 113 ms 12840 KB Partially correct
13 Partially correct 136 ms 12840 KB Partially correct
14 Partially correct 163 ms 12840 KB Partially correct
15 Partially correct 173 ms 12840 KB Partially correct
16 Partially correct 206 ms 12840 KB Partially correct
17 Partially correct 199 ms 12840 KB Partially correct
18 Partially correct 203 ms 12840 KB Partially correct
19 Partially correct 179 ms 12840 KB Partially correct
20 Partially correct 229 ms 12840 KB Partially correct