oj.uz

Submission #974967

# Submission time Handle Problem Language Result Execution time Memory
974967 2024-05-04T08:12:27 Z Kenjikrab Boat (APIO16_boat) C++14
9 / 100
 2000 ms 211980 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int const mod=1e9+7;
map<int,int> ind;
vector<int> val;
vector<int> fen(1010,0);
void upd(int idx,int val)
{
    idx+=2;
    for(int i=idx;i<1010;i+=i&-i)fen[i]+=val,fen[i]%=mod;
}
int qr(int idx)
{
    idx+=2;
    int ret=0;
    for(int i=idx;i>0;i-=i&-i)ret+=fen[i],ret%=mod;
    return ret;
}
int pow(int a,int b)
{
    if(b==0)return 1;
    if(b==1)return a;
    int ret=pow(a,b/2);
    if(b%2==0)return (ret*ret)%mod;
    else return (((ret*ret)%mod)*a)%mod;
}
map<int,int> inverse;
int inv(int a)
{
    if(inverse[a]!=0)return inverse[a];
    inverse[a]=pow(a,mod-2);
    return inverse[a];
}

map<pii,int> chos;
int choose(int a,int b)
{
    if(b>a)return 0;
    int ret=1;
    if(chos[{a,b}]!=0)return chos[{a,b}];
    for(int i=b+1;i<=a;i++)
    {
        ret*=i;
        ret%=mod;
    }
    for(int i=2;i<=a-b;i++)
    {
        ret*=inv(i);
        ret%=mod;
    }
    chos[{a,b}]=ret;
    return ret;
}

signed main()
{
    int n;
    cin>>n;
    vector<pii> info;
    set<int> temp;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        temp.insert(a);
        temp.insert(b+1);
        info.push_back({a,b+1});
    }
    for(auto it:temp)
    {
        val.push_back(it);
        ind[it]=val.size()-1;
        //cout<<it<<" "<<ind[it]<<endl;
    }
    vector<vector<int>> pre(510,vector<int>(1010,-2));
    vector<int> latest(1010,-1);
    upd(-1,1);
    vector<vector<int>> dp(510,vector<int>(1010,0));
    for(int i=0;i<n;i++)
    {
        //cout<<endl<<i<<":";
        for(int j=ind[info[i].se]-1;j>=ind[info[i].fi];j--)
        {
            //cout<<j<<" ";
            
            int bef=latest[j];
            pre[i][j]=latest[j];
            latest[j]=i;
            int a=qr(j),b=(val[j+1]-val[j]),c=0;
            dp[i][j]=a;
            int ans=a*b;
            ans%=mod;
            int k=2;
            //cout<<i<<" "<<j<<" "<<ans<<" ";
            while(bef!=-1)
            {
                ans+=dp[bef][j]*choose(b+k-2,k);
                ans%=mod;
                bef=pre[bef][j];
                k++;
                //cout<<endl<<bef<<" "<<ans<<" ";
            }
           // cout<<endl;
            upd(j+1,ans);
        }
    }
    cout<<(qr(1007)+mod-1)%mod;
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:93:45: warning: unused variable 'c' [-Wunused-variable]
   93 |             int a=qr(j),b=(val[j+1]-val[j]),c=0;
      |                                             ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 5 ms 8676 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 5 ms 8652 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 4 ms 8688 KB Output is correct
14 Correct 4 ms 8540 KB Output is correct
15 Correct 4 ms 8540 KB Output is correct
16 Correct 4 ms 8792 KB Output is correct
17 Correct 4 ms 8540 KB Output is correct
18 Correct 4 ms 8540 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8540 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 5 ms 8676 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 5 ms 8652 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 4 ms 8688 KB Output is correct
14 Correct 4 ms 8540 KB Output is correct
15 Correct 4 ms 8540 KB Output is correct
16 Correct 4 ms 8792 KB Output is correct
17 Correct 4 ms 8540 KB Output is correct
18 Correct 4 ms 8540 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8540 KB Output is correct
21 Correct 1512 ms 9204 KB Output is correct
22 Correct 1371 ms 9300 KB Output is correct
23 Correct 1260 ms 9044 KB Output is correct
24 Correct 1534 ms 9504 KB Output is correct
25 Correct 1602 ms 9228 KB Output is correct
26 Execution timed out 2025 ms 9320 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 5 ms 8676 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 5 ms 8652 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 4 ms 8688 KB Output is correct
14 Correct 4 ms 8540 KB Output is correct
15 Correct 4 ms 8540 KB Output is correct
16 Correct 4 ms 8792 KB Output is correct
17 Correct 4 ms 8540 KB Output is correct
18 Correct 4 ms 8540 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8540 KB Output is correct
21 Correct 1512 ms 9204 KB Output is correct
22 Correct 1371 ms 9300 KB Output is correct
23 Correct 1260 ms 9044 KB Output is correct
24 Correct 1534 ms 9504 KB Output is correct
25 Correct 1602 ms 9228 KB Output is correct
26 Execution timed out 2025 ms 9320 KB Time limit exceeded
27 Halted 0 ms 0 KB -