oj.uz

Submission #487447

# Submission time Handle Problem Language Result Execution time Memory
487447 2021-11-15T14:35:50 Z leaked Boat (APIO16_boat) C++14
9 / 100
 235 ms 6296 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
const int M=1e9+7;
const int N=5e2+10;
const int Mx=3+1;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
int inv[N];
int gi(int x){
    if(!inv[x]) inv[x]=binpow(x,M-2);
    return inv[x];
}
//int C(int k,int n){
//    if(k>n) return 0;
//    int ans=1;
//    for(int i=n-k+1;i<=n;i++) ans=mult(ans,i);
//    for(int i=1;i<=k;i++) ans=mult(ans,gi(i));
//    return ans;
//}
signed main(){
    fast_iati;
    int tests=1;
    while(tests--){
        int n=2;
        cin>>n;
        vec<int>a(n),b(n);
        vec<int> kek;
        for(int i=0;i<n;i++) {
            cin>>a[i]>>b[i];
//            a[i]=rand()%Mx+1,b[i]=rand()%Mx+1;
//            if(a[i]>b[i]) swap(a[i],b[i]);
            kek.pb(a[i]-1),kek.pb(b[i]);
        }
        vec<int>l,r;l=a;r=b;
        auto solve=[&](){
            kek.pb(0);sort(all(kek));kek.erase(unique(all(kek)),kek.end());
            vec<vec<int>>dp(n+1,vec<int>(sz(kek)+1,0));
            vec<vec<int>>pref(n+1,vec<int>(sz(kek)+1,0));
            vec<int>ways(sz(kek));
            vec<vec<int>>col(sz(kek),vec<int>(n+1,0));
            for(int i=1;i<sz(kek);i++){
                ways[i]=kek[i]-kek[i-1];
                vec<int> ct(n+1,0);
                ct[0]=1;
                for(int j=1;j<=n;j++){
                    if(j>ways[i]) ct[j]=0;
                    else{
                        ct[j]=mult(ct[j-1],ways[i]-j+1);
                        ct[j]=mult(ct[j],gi(j));
                    }
//                    cout<<"DEBUGFGEEGEGE"<<"C "<<j<<' '<<ways[i]<<' '<<ct[j]<<' '<<gendl;
                }
                /// so
                col[i][2]=ct[2];
//                cout<<ct[2]<<endl;
//                cout<<endl;

                for(int j=3;j<=n;j++){
                    col[i][j]=col[i][j-1];
                    col[i][j]=mult(col[i][j],j-2);
                    add(col[i][j],ct[j]);
//                    cout<<"DEBIL "<<ways[i]<<' '<<j<<' '<<col[i][j]<<endl;
                }
            }
            for(int j=0;j<sz(kek);j++) pref[0][j]=1;
            for(int i=0;i<n;i++){
                a[i]=lower_bound(all(kek),a[i]-1)-kek.begin()+1;
                b[i]=lower_bound(all(kek),b[i])-kek.begin();
            }
            for(int i=0;i<n;i++){
                for(int j=a[i];j<=b[i];j++){
                    /// I start with me
                    /// then it's pref[i][j-1]
                    add(dp[i+1][j],mult(ways[j],pref[i][j-1]));
//                    if(i==1)cout<<"ALO "<<pref[i][j-1]<<endl;
                    if(ways[j]>=2){
                        int cnt=1;
                        for(int k=i-1;k>=0;k--){
                            if(a[k]>j || b[k]<j) continue;
                            cnt++;
//                            cout<<"CHECK "<<i<<' '<<k<<' '<<j<<' '<<' '<<col[j][i-k+1]<<endl;
                            add(dp[i+1][j],mult(col[j][cnt],pref[k][j-1]));
                        }
                    }
                }
//                 for(int j=0;j<sz(kek);j++){
//                    cout<<"DEBUG "<<(j?kek[j-1]+1:0)<<' '<<kek[j]<<' '<<dp[i+1][j]<<endl;
//                }
//                cout<<endl;
                for(int j=0;j<sz(kek);j++){
                    pref[i+1][j]=dp[i+1][j];
                    if(j)add(pref[i+1][j],pref[i+1][j-1]);
                }
                for(int j=0;j<sz(kek);j++){
                    add(pref[i+1][j],pref[i][j]);
                }
            }
            return pref[n][sz(kek)-1];
        };
        auto stupid=[&](){
            vec<vec<int>>dp1(n+1,vec<int>(Mx+1,0));
            for(int j=0;j<=Mx;j++) dp1[0][j]=1;
            for(int i=0;i<n;i++){
//                cout<<"AUE "<<l[i]<<' '<<r[i]<<endl;
                for(int x=l[i];x<=r[i];x++){
                    add(dp1[i+1][x],dp1[i][x-1]);
                }
                for(int j=1;j<=Mx;j++) add(dp1[i+1][j],dp1[i+1][j-1]);
                for(int j=0;j<=Mx;j++){
                    add(dp1[i+1][j],dp1[i][j]);
                }
            }
            return dp1[n][Mx];
        };
        int rans=solve();
        add(rans,-1);
        cout<<rans;
//        cout<<"SOL "<<stupid()<<' '<<solve()<<endl;
//        if(stupid()!=solve()){
//            cout<<stupid()<<' '<<solve()<<endl;
//            cout<<n<<endl;
//            for(int i=0;i<n;i++) cout<<l[i]<<' '<<r[i]<<endl;
//            return 0;
//        }
    }
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:131:14: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  131 |         auto stupid=[&](){
      |              ^~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6296 KB Output is correct
2 Correct 14 ms 6252 KB Output is correct
3 Correct 14 ms 6220 KB Output is correct
4 Correct 14 ms 6220 KB Output is correct
5 Correct 14 ms 6220 KB Output is correct
6 Correct 14 ms 6220 KB Output is correct
7 Correct 15 ms 6220 KB Output is correct
8 Correct 15 ms 6220 KB Output is correct
9 Correct 14 ms 6220 KB Output is correct
10 Correct 14 ms 6220 KB Output is correct
11 Correct 16 ms 6220 KB Output is correct
12 Correct 14 ms 6220 KB Output is correct
13 Correct 14 ms 6220 KB Output is correct
14 Correct 14 ms 6220 KB Output is correct
15 Correct 15 ms 6220 KB Output is correct
16 Correct 3 ms 1356 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 4 ms 1356 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 3 ms 1356 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6296 KB Output is correct
2 Correct 14 ms 6252 KB Output is correct
3 Correct 14 ms 6220 KB Output is correct
4 Correct 14 ms 6220 KB Output is correct
5 Correct 14 ms 6220 KB Output is correct
6 Correct 14 ms 6220 KB Output is correct
7 Correct 15 ms 6220 KB Output is correct
8 Correct 15 ms 6220 KB Output is correct
9 Correct 14 ms 6220 KB Output is correct
10 Correct 14 ms 6220 KB Output is correct
11 Correct 16 ms 6220 KB Output is correct
12 Correct 14 ms 6220 KB Output is correct
13 Correct 14 ms 6220 KB Output is correct
14 Correct 14 ms 6220 KB Output is correct
15 Correct 15 ms 6220 KB Output is correct
16 Correct 3 ms 1356 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 4 ms 1356 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 3 ms 1356 KB Output is correct
21 Incorrect 235 ms 5708 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6296 KB Output is correct
2 Correct 14 ms 6252 KB Output is correct
3 Correct 14 ms 6220 KB Output is correct
4 Correct 14 ms 6220 KB Output is correct
5 Correct 14 ms 6220 KB Output is correct
6 Correct 14 ms 6220 KB Output is correct
7 Correct 15 ms 6220 KB Output is correct
8 Correct 15 ms 6220 KB Output is correct
9 Correct 14 ms 6220 KB Output is correct
10 Correct 14 ms 6220 KB Output is correct
11 Correct 16 ms 6220 KB Output is correct
12 Correct 14 ms 6220 KB Output is correct
13 Correct 14 ms 6220 KB Output is correct
14 Correct 14 ms 6220 KB Output is correct
15 Correct 15 ms 6220 KB Output is correct
16 Correct 3 ms 1356 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 4 ms 1356 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 3 ms 1356 KB Output is correct
21 Incorrect 235 ms 5708 KB Output isn't correct
22 Halted 0 ms 0 KB -