제출 #145567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145567		MKopchev	사다리꼴 (balkan11_trapezoid)	C++14	100 / 100	171 ms	8952 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42,mod=30013;
struct rect
{
    int a,b,c,d;
    int id;
};
bool cmp(rect a,rect b)
{
    return a.b<b.b;
}
bool cmp_2(rect a,rect b)
{
    return a.d<b.d;
}
int n;
rect inp[nmax];
pair<int/*maximum*/,int/*times*/> dp[nmax];
pair<int/*up to*/,int/*original id*/> seen[nmax];

pair<int/*maximum*/,int/*times*/> tree[4*nmax];

pair<int/*maximum*/,int/*times*/> my_merge(pair<int/*maximum*/,int/*times*/> a,pair<int/*maximum*/,int/*times*/> b)
{
    if(a.first>b.first)return a;
    if(a.first<b.first)return b;
    a.second=(a.second+b.second)%mod;
    return a;
}
pair<int/*maximum*/,int/*times*/> query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];
    pair<int/*maximum*/,int/*times*/> ret={0,0};
    int av=(l+r)/2;
    if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
    return ret;
}
void update(int node,int l,int r,int pos,pair<int/*maximum*/,int/*times*/> val)
{
    if(l==r)
    {
        tree[node]=val;
        return;
    }
    int av=(l+r)/2;
    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);
    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
int where[nmax];
int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%i%i%i%i",&inp[i].a,&inp[i].b,&inp[i].c,&inp[i].d);
        dp[i]={1,1};
    }
    sort(inp+1,inp+n+1,cmp);

    for(int i=1;i<=n;i++)
        inp[i].id=i;

    for(int i=1;i<=n;i++)
    {
        int ok=0,not_ok=i;
        while(not_ok-ok>1)
        {
            int av=(ok+not_ok)/2;
            if(inp[av].b<inp[i].a)ok=av;
            else not_ok=av;
        }
        seen[i]={ok,i};
        //cout<<i<<" -> "<<ok<<" "<<i<<endl;
    }
    sort(seen+1,seen+n+1);

    sort(inp+1,inp+n+1,cmp_2);

    for(int i=1;i<=n;i++)
        where[inp[i].id]=i;

    int j=1;
    for(int i=0;i<=n;i++)
    {
        if(i)
        {
            int id=i;
            int pos=where[id];
            update(1,1,n,pos,dp[id]);
        }

        while(j<=n&seen[j].first==i)
        {
            int id=seen[j].second;

            int pos=where[id];

            int ok=0,not_ok=n+1;
            while(not_ok-ok>1)
            {
                int av=(ok+not_ok)/2;
                if(inp[av].d<inp[pos].c)ok=av;
                else not_ok=av;
            }
            if(ok==0)dp[id]={1,0};
            else
            {
                dp[id]=query(1,1,n,1,ok);
                dp[id].first++;
            }

            if(dp[id]==make_pair(1,0))dp[id]={1,1};

            j++;

            //cout<<id<<" -> "<<dp[id].first<<" "<<dp[id].second<<endl;
        }
    }

    //inp[j].d<inp[i].c

    int maxi=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        if(dp[i].first>maxi)
        {
            maxi=dp[i].first;
            sum=dp[i].second;
        }
        else if(dp[i].first==maxi)
        {
            sum=(sum+dp[i].second)%mod;
        }
    }

    printf("%i %i\n",maxi,sum);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:95:16: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
         while(j<=n&seen[j].first==i)
               ~^~~
trapezoid.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
trapezoid.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i%i",&inp[i].a,&inp[i].b,&inp[i].c,&inp[i].d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100