Submission #1310465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310465		danglayloi1	Boat (APIO16_boat)	C++20	9 / 100	4 ms	608 KiB

boat

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e3+5;
int add(int a, int b)
{
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int mul(int a, int b)
{
    ll tmp=1ll*a*b;
    if(tmp>=mod) tmp%=mod;
    return tmp;
}
int n, m, bit[nx], tmp[nx];
ii a[nx];
vector<int> rar;
void upd(int x, int val)
{
    for(; x <= m; x+=x&-x)
        bit[x]=add(bit[x], val);
}
int get(int x)
{
    int res=0;
    for(; x > 0; x-=x&-x)
        res=add(res, bit[x]);
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i].fi>>a[i].se;
        rar.emplace_back(a[i].fi);
        rar.emplace_back(a[i].se);
        rar.emplace_back(a[i].se+1);
    }
    sort(rar.begin(), rar.end());
    rar.erase(unique(rar.begin(), rar.end()), rar.end());
    m=rar.size();
    for(int i = 1; i <= n; i++)
    {
        a[i].fi=upper_bound(rar.begin(), rar.end(), a[i].fi)-rar.begin();
        a[i].se=upper_bound(rar.begin(), rar.end(), a[i].se)-rar.begin();
        for(int j = a[i].fi; j <= a[i].se; j++)
        {
            int len=rar[j]-rar[j-1];
            tmp[j]=mul(len, get(j-1));
            tmp[j]=add(tmp[j], 1);
        }
        for(int j = a[i].fi; j <= a[i].se; j++)
        {
            int len=rar[j]-rar[j-1];
            upd(j, tmp[j]);
        }
    }
    cout<<get(m);
}

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