Submission #1301755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301755		tdkhai	Boat (APIO16_boat)	C++20	0 / 100	1 ms	332 KiB

boat

/*
        _.-- ,.--.
      .'   .'     /
       @       |'..--------._
     /      \._/              '.
    /  .-.-                     \
   (  /    \                     \
   \\      '.                  | #
    \\       \   -.           /
     :\       |    )._____.'   \
      "       |   /  \  |  \    )
              |   |./'  :__ \.-'
              '--'
*/
#include<bits/stdc++.h>
#define ll long long
#define llll pair<ll,ll>
#define ii pair<int,int>
#define fi first
#define se second
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define ull unsigned long long
#define iii pair<int,ii>
#define iv pair<pii,ii>
#define db double
#define ld long double
#define pb push_back
#define tdk "kfph"


using namespace std;

const int dx[]  = {1, -1, 0, 0};
const int dy[]  = {0, 0, -1, 1};
const int dxx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyy[] = {2, -2, 2, -2, 1, -1, 1, -1};
const ll INF=1e18;


const int N=505;
const int mod=1e9+7;
int add(int a,int b)
{
    return (a+b)%mod;
}
int mul(int a,int b)
{
    return 1ll*a*b%mod;
}
int sub(int a,int b)
{
    return ((a-b)%mod+mod)%mod;
}
namespace fenwick
{
    int ft[N*4];
    void init()
    {
        memset(ft,0,sizeof ft);
    }
    void update(int u,int val)
    {
        while(u<N*4)
        {
            ft[u]=add(ft[u],val);
            u+=u&-u;
        }
    }
    int get(int u)
    {
        int ret=0;
        while(u)
        {
            ret=add(ret,ft[u]);
            u-=u&-u;
        }
        return ret;
    }
}
using namespace fenwick;
int dp[N][N*4],n,a[N],b[N],ans=0;
vector<int> val;
void kfph()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i] >> b[i];
        val.pb(a[i]);
        val.pb(b[i]);
        val.pb(a[i]-1);
        val.pb(b[i]-1);
    }
    val.pb(0);
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    init();
    update(1,1);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin()+1;
        b[i]=lower_bound(val.begin(),val.end(),b[i])-val.begin()+1;
//        cout << a[i] << ' ' << b[i] << '\n';
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][1]=get(val.size())-get(1);
//        cout << dp[i][1] << '\n';
        dp[i][a[i]]=get(val[a[i]]-1);
        for(int j=a[i]+1;j<=b[i];j++)
        {
            dp[i][j]=(val[j-1]-val[j-2])*get(val[j-2]);
        }
        update(1,dp[i][1]);
        for(int j=a[i];j<=b[i];j++)
        {
            update(j,dp[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=val.size();j++)
        {
//            cout << dp[i][j] << " \n"[j==val.size()];
            ans=add(ans,dp[i][j]);
        }
    }
    cout << sub(ans,1);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(tdk".inp","r"))
    {
        freopen(tdk".inp","r",stdin);
        freopen(tdk".out","w",stdout);
    }
    int t=1;
    //cin >> t;
    while(t--)
    {
        kfph();
    }
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(tdk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
boat.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(tdk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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