Submission #974897

#TimeUsernameProblemLanguageResultExecution timeMemory
974897KenjikrabBoat (APIO16_boat)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define fi first #define se second using namespace std; ll const mod=1e9+7; map<ll,ll> index; vector<ll> val; vector<ll> fen(1010,0); void upd(int idx,ll val) { idx+=2; for(int i=idx;i<1010;i+=i&-i)fen[i]+=val,fen[i]%=mod; } int qr(int idx) { idx+=2; ll ret=0; for(int i=idx;i>0;i-=i&-i)ret+=fen[i],ret%=mod; return ret; } int pow(ll a,ll b) { if(b==0)return 1; if(b==1)return a; ll ret=pow(a,b/2); if(b%2==0)return (ret*ret)%mod; else return (((ret*ret)%mod)*a)%mod; } map<ll,ll> inverse; ll inv(ll a) { if(inverse[a]!=0)return inverse[a]; inverse[a]=pow(a,mod-2); return inverse[a]; } ll choose(ll a,ll b) { if(b>a)return 0; ll ret=1; 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; } return ret; } signed main() { int n; cin>>n; vector<pii> info; set<int> temp; for(int i=0;i<n;i++) { ll 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); index[it]=val.size()-1; //cout<<it<<" "<<index[it]<<endl; } vector<vector<int>> pre(510,vector<int>(1010,-2)); vector<int> latest(1010,-1); for(int i=0;i<n;i++) { for(int j=index[info[i].fi];j<index[info[i].se];j++) { pre[i][j]=latest[j]; latest[j]=i; } } upd(-1,1); vector<vector<ll>> dp(510,vector<ll>(1010,0)); for(int i=0;i<n;i++) { //cout<<endl<<i<<":"; for(int j=index[info[i].se]-1;j>=index[info[i].fi];j--) { //cout<<j<<" "; ll a=qr(j),b=(val[j+1]-val[j]); dp[i][j]=a; ll ans=a*b; ans%=mod; int bef=pre[i][j],k=2; while(bef!=-1) { ans+=dp[bef][j]*choose(b,k); ans%=mod; bef=pre[bef][j]; k++; } upd(j+1,ans); //cout<<i<<" "<<j<<" "<<ans<<endl; } } cout<<(qr(1005)+mod-1)%mod; return 0; }

Compilation message (stderr)

boat.cpp:8:12: error: 'std::map<long long int, long long int> index' redeclared as different kind of entity
    8 | map<ll,ll> index;
      |            ^~~~~
In file included from /usr/include/string.h:432,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from boat.cpp:1:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
boat.cpp: In function 'int main()':
boat.cpp:71:14: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   71 |         index[it]=val.size()-1;
      |              ^
boat.cpp:78:24: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   78 |         for(int j=index[info[i].fi];j<index[info[i].se];j++)
      |                        ^
boat.cpp:78:44: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   78 |         for(int j=index[info[i].fi];j<index[info[i].se];j++)
      |                                            ^
boat.cpp:89:24: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   89 |         for(int j=index[info[i].se]-1;j>=index[info[i].fi];j--)
      |                        ^
boat.cpp:89:47: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   89 |         for(int j=index[info[i].se]-1;j>=index[info[i].fi];j--)
      |                                               ^