oj.uz

Submission #12170

# Submission time Handle Problem Language Result Execution time Memory
12170 2014-12-21T14:14:55 Z dohyun0324 trapezoid (balkan11_trapezoid) C++
59 / 100
 236 ms 27684 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int dap,t=1,w,n,tree[800010],d[200010],s1[800010],s2[800010];
long long sum,cnt[800010],d2[800010];
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));
}
long long query2(int a,int b,int x,int y,int k)
{
    if(a<=x && y<=b) return cnt[k];
    if(a>y || x>b) return 0;
    s1[k]=query(a,b,x,(x+y)/2,k*2); s2[k]=query(a,b,(x+y)/2+1,y,k*2+1);
    if(s1[k]==s2[k]) return query2(a,b,x,(x+y)/2,k*2)+query2(a,b,(x+y)/2+1,y,k*2+1);
    else if(s1[k]>s2[k]) 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]; sum%=30013;}
        if(dap<d[i])
        {
            dap=d[i];
            sum=d2[i];
        }
    }
    printf("%d %lld",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
59.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27684 KB Output is correct
2 Correct 0 ms 27684 KB Output is correct
3 Correct 0 ms 27684 KB Output is correct
4 Partially correct 0 ms 27684 KB Partially correct
5 Correct 0 ms 27684 KB Output is correct
6 Partially correct 3 ms 27684 KB Partially correct
7 Partially correct 6 ms 27684 KB Partially correct
8 Correct 6 ms 27684 KB Output is correct
9 Correct 23 ms 27684 KB Output is correct
10 Partially correct 43 ms 27684 KB Partially correct
11 Partially correct 46 ms 27684 KB Partially correct
12 Partially correct 123 ms 27684 KB Partially correct
13 Incorrect 136 ms 27684 KB Expected int32, but "-4195152448689438272" found
14 Partially correct 169 ms 27684 KB Partially correct
15 Partially correct 179 ms 27684 KB Partially correct
16 Correct 203 ms 27684 KB Output is correct
17 Partially correct 213 ms 27684 KB Partially correct
18 Partially correct 206 ms 27684 KB Partially correct
19 Partially correct 186 ms 27684 KB Partially correct
20 Partially correct 236 ms 27684 KB Partially correct