| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1370556 | kaorin | Boat (APIO16_boat) | C++20 | 0 ms | 0 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() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
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;
}