제출 #257947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257947		daniel920712	Boat (APIO16_boat)	C++14	31 / 100	550 ms	159212 KiB

boat

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <time.h>

using namespace std;
long long MOD=1e9+7,now=1;
long long a[505];
long long b[505];
struct A
{
    long long l,r;
    long long nxl,nxr;
    long long con;
}Node[2000005];
void build(long long l,long long r,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].con=0;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
}
long long Find(long long l,long long r,long long here)
{
    if(here<0) return 0;
    if(Node[here].l==l&&Node[here].r==r) return Node[here].con;
    if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
    if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
    return (Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl)+Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr))%MOD;
}
void cha(long long where,long long con,long long here)
{
    //printf("%lld %lld %lld %lld %lld\n",where,con,here,Node[here].l,Node[here].r);
    Node[here].con+=con;
    Node[here].con%=MOD;

    if(Node[here].l==where&&Node[here].r==where)
    {

        return;
    }
    if(where<=(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            build(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl);
        }
        cha(where,con,Node[here].nxl);
    }
    else
    {
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            build((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr);
        }
        cha(where,con,Node[here].nxr);
    }
}
int main()
{

    //srand(time(NULL));
    long long N,M,i,j;
    scanf("%lld",&N);
    for(i=1;i<=N;i++) scanf("%lld %lld",&a[i],&b[i]);
    build(0,1e9,0);
    cha(0,1,0);
    //printf("aa\n");
    for(i=1;i<=N;i++)
    {
        for(j=b[i];j>=a[i];j--)
        {
            //printf("%lld %lld\n",i,j);
            cha(j,Find(0,j-1,0),0);
        }
    }

    printf("%lld\n",Find(1,1e9,0));
    return 0;
}
/*
2
32 47
18 78
*/

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

boat.cpp: In function 'int main()':
boat.cpp:68:17: warning: unused variable 'M' [-Wunused-variable]
     long long N,M,i,j;
                 ^
boat.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
     ~~~~~^~~~~~~~~~~
boat.cpp:70:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=N;i++) scanf("%lld %lld",&a[i],&b[i]);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42