oj.uz

답안 #145567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145567 2019-08-20T12:04:03 Z MKopchev 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 171 ms 8952 KB 
#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;
}

Compilation message

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 9 ms 804 KB Output is correct
9 Correct 16 ms 1224 KB Output is correct
10 Correct 27 ms 2296 KB Output is correct
11 Correct 36 ms 2652 KB Output is correct
12 Correct 80 ms 4728 KB Output is correct
13 Correct 98 ms 5320 KB Output is correct
14 Correct 118 ms 7136 KB Output is correct
15 Correct 133 ms 7388 KB Output is correct
16 Correct 142 ms 7644 KB Output is correct
17 Correct 147 ms 8056 KB Output is correct
18 Correct 122 ms 8312 KB Output is correct
19 Correct 146 ms 8640 KB Output is correct
20 Correct 171 ms 8952 KB Output is correct