oj.uz

Submission #978281

# Submission time Handle Problem Language Result Execution time Memory
978281 2024-05-09T05:13:41 Z Amr Boat (APIO16_boat) C++17
0 / 100
 2000 ms 920 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=204;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)   % mod;
        y = y>>1;
        x = (x*x)  % mod;
    }
    return res;
}
ll a[N] , b[N];
map<ll,ll> com;
ll recom[N];
ll siz[N];
ll dp[N][N];
ll ch[N][N];
ll ch2[N][N];
ll p[N];
ll bit[2*N];
ll n;
void upd(ll x, ll val)
{
    while(x < N)
    {
        bit[x] = (bit[x] + val)%mod;
        x += x&(-x);
    }
}
ll get(ll x)
{
    ll res = 0;
    while(x)
    {
        res+=bit[x];
        x -= x&(-x);
    }
    return res%mod;
}
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    p[0] = 1;
    for(int i = 1; i < N; i++) p[i] = (p[i-1]*i)%mod;

    for(int i = 1; i <= n; i++) com[a[i]] = 1, com[b[i]+1] = 1;
    ll l = 1;
    for(auto it: com)
    {
        com[it.F] = l;
        recom[l++] = it.F;
    }
    for(int i = 1; i <= 2*n; i++) siz[i] = recom[i+1]-recom[i];
   // for(int i = 1; i <= 2*n; i++) cout << recom[i] << " "; cout << endl;

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            ll above = p[i];
            ll down = p[j]*p[i-j];
            ch[i][j] = above*power(down,mod-2);
        }
    }
    for(int i = 1; i <= 2*n; i++)
    {
        if(recom[i+1]==0) continue;
        for(int j = 0; j <= siz[i]; j++)
        {
            ll above = 1;

            for(int k = siz[i];  k > siz[i]-j; k--) above = (above*k)%mod;
            ll down = p[j];
            ch2[i][j] = (above*power(down,mod-2))%mod;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        ll curend = com[b[i]+1];
        ll curstart = com[a[i]];
        for(int j = curend-1; j>= curstart; j--)
        {
            dp[i][j] = get(j-1);
            ll something = 0;
            //
            ll cnt = 0;
            for(int k = i; k >= 1; k--)
            {
                if(com[a[k]]<=j&&com[b[k]+1]>j)  {cnt++;} else continue;
                for(int kk = 1; kk <= cnt; kk++) { something = (something +ch[cnt-2+1*(k==i)][kk-2+(k==i)]*ch2[k][kk]);}
            }

          //  cout << something << endl;
            upd(j,something%mod+dp[i][j]);
        }
    }
    cout << get(2*n+1) << endl;


}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("friday.out","w",stdout);
    fast;
    while(TT--)
        solve();

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -