Submission #1370557

#TimeUsernameProblemLanguageResultExecution timeMemory
1370557kaorinBoat (APIO16_boat)C++20
Compilation error
0 ms0 KiB
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll mod = 1e9+7;

ll inv[1000];

ll sigma(ll n, const vector<ll>& k){
    ll ret=0,now=1;
    for(int i=0; i<k.size(); i++){
        now=now*(n++)%mod*inv[i+1]%mod;
        ret = (ret + now*k[i])%mod;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    inv[0]=inv[1]=1;
    for(int i = 2; i<1000; i++) inv[i]=mod-(mod/i)*inv[mod%i]%mod;

    int a;
    cin>>a;
    
    vector<pair<pii,vector<ll>>> k; 
    
    ll ans=0;
    for(int i=0; i<a; i++){
        int x,y;
        cin>>x>>y;
        if(k.empty()) {
            k.push_back({{x,y},{1}});
            ans += y-x+1;
        }
        else{
            vector<pair<pii,vector<ll>>> ka;
            ka.reserve(k.size() * 2 + 5);
            ll w=0;

            for(auto& u:k){
                auto [l,r]=u.first;
                if(r<x){
                    w = (w + sigma(r,u.second) -sigma(l-1,u.second))%mod;
                    ka.push_back(move(u));
                }
                else if(y<l){
                    if(x<=y) ka.push_back({{x,y},{1+w}}),ans=(ans+(y-x+1)*(w+1))%mod,x=y+1;
                    ka.push_back(move(u));
                }

                else{
                    if(x<l) ka.push_back({{x,l-1},{1+w}}),ans=(ans+(l-x)*(w+1))%mod,x=l;

                    ll xu = sigma(x-1,u.second);
                    w = (w + xu - sigma(l-1,u.second))%mod;
                    if(x!=l) ka.push_back({{l,x-1},{u.second}}),l=x;

                    ll sz = u.second.size();
                    vector<ll> kaa(sz+1);
                    kaa[0] = (w+1-xu-u.second[0])%mod;
                    for(int i=1; i<sz; i++) kaa[i]=(u.second[i-1]-u.second[i])%mod;
                    kaa[sz]=u.second[sz-1];

                    ll xk = sigma(x-1,kaa);
                    if(y>r){
                        ans = (ans + sigma(r,kaa)-xk)%mod; 
                        for(int i=0; i<u.second.size(); i++) kaa[i]=(kaa[i]+u.second[i])%mod;
                        w = (w+sigma(r,u.second)-xu)%mod;
                        ka.push_back({{x,r},move(kaa)});
                        x = r+1;                      
                    }else{
                        ans = (ans + sigma(y,kaa)-xk)%mod;
                        for(int i=0; i<u.second.size(); i++) kaa[i]=(kaa[i]+u.second[i])%mod;
                        ka.push_back({{x,y},move(kaa)});
                        x=y+1;
                        if(y!=r) ka.push_back({{x,r},u.second});
                    }
                }
            }
            if(x<=y) ka.push_back({{x,y},{1+w}}),ans=(ans+(w+1)*(y-x+1))%mod;
            k = move(ka);
        }
    }
    cout<<(ans+mod)%mod;
}

Compilation message (stderr)

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from boat.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor 'constexpr std::_Vector_base<std::pair<std::pair<int, int>, std::vector<long long int> >, std::allocator<std::pair<std::pair<int, int>, std::vector<long long int> > > >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<std::pair<int, int>, std::vector<long long int> >]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~