Submission #1048088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1048088	2024-08-07T22:14:15 Z	HossamHero7	Boat (APIO16_boat)	C++17	Compilation error	0 ms	0 KB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int mod = 1e9 + 7;
int add(int a,int b){
    return (a + b >= mod ? a + b - mod : a + b);
}
int sub(int a,int b){
    return (a - b >= 0 ? a - b : a - b + mod);
}
int mult(ll a,ll b){
	return (a*b)%mod;
}
int power(int a,int b){
	if(b == 0) return 1;
	if(b == 1) return a;
	int r = power(a,b/2);
	if(b&1) return mult(mult(r,r),a);
	return mult(r,r);
}
int divide(int a,int b){
    return mult(a , power(b,mod-2));
}
int dp[2][505];
void solve(){
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    vector<int> v;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        v.push_back(a[i]);
        v.push_back(b[i]+1);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()) , v.end());
    int new_n = v.size();
    vector<vector<int>> idx(new_n+1);
    for(int i=0;i<n;i++){
        int l = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
        int r = upper_bound(v.begin(),v.end(),b[i]) - v.begin();
        for(int j=l;j<r;j++){
            idx[j].push_back(i+1);
        }
    }
    vector<int> inv(n+1);
    for(int i=1;i<=n;i++) inv[i] = divide(1,i);
    for(int i=1;i<=n;i++) dp[new_n&1][i] = 1;
    for(int j=new_n-1;j>=0;j--){
        int sz = idx[j].size();
        int dp2[2][sz+1]{};
        for(int i=sz-1;i>=0;i--){
            for(int k=1;k<=sz;k++){
                if(k == 1) dp2[i&1][k] = add(dp2[i&1][k] , dp[j+1&1][idx[j][i]]);
                else dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k-1]);
                dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k]);
            }
        }
        for(int i=0;i<=n;i++){
            int gap = (j < new_n - 1 ? v[j+1] - v[j] : 0);
            sz = min(sz , gap);
            int x = 1;
            int st = upper_bound(idx[j].begin(),idx[j].end(),i) - idx[j].begin();
            dp[j&1][i] = dp[j+1&1][i];
            for(int k=1;k<=sz;k++){
                x = mult(x , gap-k+1);
                x = mult(x , inv[k]);
                dp[j&1][i] = add(dp[j&1][i],mult(dp2[st][k],x));
            }
        }
    }
    cout<<dp[0][0]<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

boat.cpp: In function 'void solve()':
boat.cpp:55:64: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   55 |                 if(k == 1) dp2[i&1][k] = add(dp2[i&1][k] , dp[j+1&1][idx[j][i]]);
      |                                                               ~^~
boat.cpp:56:59: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   56 |                 else dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k-1]);
      |                                                          ~^~
boat.cpp:57:54: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   57 |                 dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k]);
      |                                                     ~^~
boat.cpp:65:30: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   65 |             dp[j&1][i] = dp[j+1&1][i];
      |                             ~^~
during RTL pass: expand
boat.cpp:52:13: internal compiler error: in make_decl_rtl, at varasm.c:1342
   52 |         int dp2[2][sz+1]{};
      |             ^~~
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-10/README.Bugs> for instructions.