oj.uz

Submission #12171

# Submission time Handle Problem Language Result Execution time Memory
12171 2014-12-21T14:17:06 Z dohyun0324 trapezoid (balkan11_trapezoid) C++
100 / 100
 223 ms 27688 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];
        cnt[p]%=30013;
        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)%30013;
        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:57:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:60: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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27688 KB Output is correct
2 Correct 0 ms 27688 KB Output is correct
3 Correct 0 ms 27688 KB Output is correct
4 Correct 0 ms 27688 KB Output is correct
5 Correct 3 ms 27688 KB Output is correct
6 Correct 3 ms 27688 KB Output is correct
7 Correct 3 ms 27688 KB Output is correct
8 Correct 6 ms 27688 KB Output is correct
9 Correct 16 ms 27688 KB Output is correct
10 Correct 36 ms 27688 KB Output is correct
11 Correct 43 ms 27688 KB Output is correct
12 Correct 113 ms 27688 KB Output is correct
13 Correct 149 ms 27688 KB Output is correct
14 Correct 146 ms 27688 KB Output is correct
15 Correct 176 ms 27688 KB Output is correct
16 Correct 209 ms 27688 KB Output is correct
17 Correct 206 ms 27688 KB Output is correct
18 Correct 213 ms 27688 KB Output is correct
19 Correct 193 ms 27688 KB Output is correct
20 Correct 223 ms 27688 KB Output is correct