oj.uz

Submission #730844

# Submission time Handle Problem Language Result Execution time Memory
730844 2023-04-26T14:12:05 Z bgnbvnbv Boat (APIO16_boat) C++14
9 / 100
 101 ms 5172 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
const int mod=(int)1e9+7;
const int maxn=2*505;
int sz,a[maxn],b[maxn];
vector<int>v,s;
int n;
vector<pll>block;
int val[maxn][maxn];
int cnt[maxn];
int add[maxn];
int chia[maxn];
int pw(int x,int y)
{
    if(y==0) return 1;
    int x1=pw(x,y/2);
    x1=x1*x1%mod;
    if(y&1) x1=x1*x%mod;
    return x1;
}
int pre[maxn];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i] >> b[i];
        v.push_back(a[i]-1);
        v.push_back(b[i]);
    }
    for(int i=1;i<=n;i++) chia[i]=pw(i,mod-2);
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        if(i==0||v[i]!=v[i-1]) s.push_back(v[i]);
    }
    swap(v,s);
    for(int i=0;i<v.size();i++)
    {
        if(i==0) block.push_back({0,v[i]});
        else block.push_back({v[i-1]+1,v[i]});
    }
    for(int i=0;i<block.size();i++) pre[i]=1;
    int tt=0,valcu;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(block.begin(),block.end(),(pll){a[i]+1,0ll})-block.begin()-1;
        b[i]=lower_bound(block.begin(),block.end(),(pll){b[i]+1,0ll})-block.begin()-1;
        //cout << a[i] <<' '<<b[i]<<'\n';
        for(int j=a[i];j<=b[i];j++)
        {
            cnt[j]++;
            val[j][cnt[j]]=pre[j-1];
            for(int k=1;k<=cnt[j];k++)
            {
                tt=cnt[j]-k+1;
                valcu=val[j][k]*(block[j].se-block[j].fi)%mod*chia[tt]%mod;
                if(j==cnt[j]) valcu=0;
                val[j][k]+=valcu;
                if(val[j][k]>=mod) val[j][k]-=mod;
                add[j]+=valcu;
                if(add[j]>=mod) add[j]-=mod;
            }
            add[j]+=val[j][cnt[j]];
            if(add[j]>=mod) add[j]-=mod;
        }
        for(int j=1;j<block.size();j++)
        {
            add[j]+=add[j-1];
            pre[j]+=add[j];
            if(pre[j]>=mod) pre[j]-=mod;
        }
        for(int j=1;j<block.size();j++) add[j]=0;
    }
    cout << (pre[block.size()-1]-1+mod)%mod;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
boat.cpp:45:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
boat.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<block.size();i++) pre[i]=1;
      |                 ~^~~~~~~~~~~~~
boat.cpp:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j=1;j<block.size();j++)
      |                     ~^~~~~~~~~~~~~
boat.cpp:80:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=1;j<block.size();j++) add[j]=0;
      |                     ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct
4 Correct 3 ms 2388 KB Output is correct
5 Correct 4 ms 2388 KB Output is correct
6 Correct 4 ms 2388 KB Output is correct
7 Correct 3 ms 2388 KB Output is correct
8 Correct 3 ms 2384 KB Output is correct
9 Correct 3 ms 2388 KB Output is correct
10 Correct 3 ms 2388 KB Output is correct
11 Correct 3 ms 2388 KB Output is correct
12 Correct 4 ms 2388 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 3 ms 2388 KB Output is correct
15 Correct 3 ms 2388 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct
4 Correct 3 ms 2388 KB Output is correct
5 Correct 4 ms 2388 KB Output is correct
6 Correct 4 ms 2388 KB Output is correct
7 Correct 3 ms 2388 KB Output is correct
8 Correct 3 ms 2384 KB Output is correct
9 Correct 3 ms 2388 KB Output is correct
10 Correct 3 ms 2388 KB Output is correct
11 Correct 3 ms 2388 KB Output is correct
12 Correct 4 ms 2388 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 3 ms 2388 KB Output is correct
15 Correct 3 ms 2388 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Incorrect 101 ms 5172 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct
4 Correct 3 ms 2388 KB Output is correct
5 Correct 4 ms 2388 KB Output is correct
6 Correct 4 ms 2388 KB Output is correct
7 Correct 3 ms 2388 KB Output is correct
8 Correct 3 ms 2384 KB Output is correct
9 Correct 3 ms 2388 KB Output is correct
10 Correct 3 ms 2388 KB Output is correct
11 Correct 3 ms 2388 KB Output is correct
12 Correct 4 ms 2388 KB Output is correct
13 Correct 4 ms 2388 KB Output is correct
14 Correct 3 ms 2388 KB Output is correct
15 Correct 3 ms 2388 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Incorrect 101 ms 5172 KB Output isn't correct
22 Halted 0 ms 0 KB -