제출 #145507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145507		MKopchev	trapezoid (balkan11_trapezoid)	C++14	50 / 100	1086 ms	5368 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42,mod=30013;
struct rect
{
    int a,b,c,d;
};
bool cmp(rect a,rect b)
{
    return a.b<b.b;
}
int n;
rect inp[nmax];
pair<int/*maximum*/,int/*times*/> dp[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++)
    {
        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;
        }

        for(int j=1;j<=ok;j++)
        if(inp[j].d<inp[i].c)
        {
            pair<int/*maximum*/,int/*times*/> now=dp[j];
            now.first++;
            if(dp[i].first<now.first)dp[i]=now;
            else if(dp[i].first==now.first)dp[i].second=(dp[i].second+now.second)%mod;
        }

    }
    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:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
trapezoid.cpp:20: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: 50 / 100