Sorry, don’t have the time to do that.
What I used is disjoint-interval structure. I don’t remember where I read about it but it’s pretty simple. The idea is to store intervals as pairs<int,int> using a set. The insertion of new intervals fuses the intervals that collide.
disjoint-intervals
struct disjoint_intervals {
set<pair<int,int>> segs;
void insert(pair<int,int> s) {
if(s.second - s.first == 0) return;
set<pair<int,int>>::iterator it, at;
at = it = segs.lower_bound(s);
if(at != segs.begin() && (--at)->second >= s.first)
s.first = at->first, --it;
for(; it != segs.end() && it->first <= s.second; segs.erase(it++))
s.second = max(s.second, it->second);
segs.insert(s);
}
};
To solve the chapter 2 of the fbk problem you need the add the perimeter while updating the intervals (bounches of “ifs” everywhere). My implementation of the solution is no clean and by sure there are much simpler approaches. It looks like this
Solution code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const ui MOD = 1E9 + 7;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
void READ(bool _local){
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
if (_local) {
string filename = "perimetric_chapter_2_input";
freopen(string(filename + ".txt").c_str(), "r", stdin);
freopen(string(filename + ".out").c_str(), "w", stdout);
}
#endif
}
ll AL[4],AH[4],AW[4],pr;
vector<ll> L,H,W;
int n,k;
void upd(int i){
int i2 = (i>1?i-2:i+k-2);
int i1 = (i>0?i-1:i+k-1);
L[i] = (AL[0] * L[i2] % AL[3] + AL[1] * L[i1] % AL[3] + AL[2])%AL[3] + 1;
H[i] = (AH[0] * H[i2] % AH[3] + AH[1] * H[i1] % AH[3] + AH[2])%AH[3] + 1;
W[i] = (AW[0] * W[i2] % AW[3] + AW[1] * W[i1] % AW[3] + AW[2])%AW[3] + 1;
}
struct cmp {
bool operator()(const ii &a, const ii &b) { return a.first < b.first; }
};
struct disjoint_intervals {
set<ii,cmp> segs;
void insert(ii s,int h) {
set<ii>::iterator it, at;
at = it = segs.lower_bound(s);
ii s0=s;
if (it!=segs.end() && it->first==s.first){
if (it->second>=s.second) return;
pr -= (h + 2LL*(it->second-it->first))%MOD;
if (pr<0) pr += MOD;
it=segs.erase(it);
}else{
if(at != segs.begin() && (--at)->second >= s.first) {
if (at->second>=s.second) return;
s.first = at->first;
pr -= (2LL*(at->second-s0.first)+h)%MOD;
if (pr<0) pr += MOD;
it=segs.erase(--it);
}else if (it==segs.end() || it->first > s.first){
pr += h;
if (pr>=MOD) pr -= MOD;
}
}
pr += (2LL *(s0.second-s0.first) + h) %MOD;
if (pr>=MOD) pr -= MOD;
for (; it != segs.end() && it->first <= s0.second; segs.erase(it++)) {
pr -= 2LL * ((it->second - it->first) + h) %MOD;
if (pr < 0) pr += MOD;
s.second = max(s.second, it->second);
}
segs.insert(s);
pr %= MOD;
if (pr<0) pr += MOD;
}
};
void docase(){
cin>>n>>k;
L.resize(k),H.resize(k),W.resize(k);
FOR(i,k) cin>>L[i];
FOR(i,4) cin>>AL[i];
FOR(i,k) cin>>W[i];
FOR(i,4) cin>>AW[i];
FOR(i,k) cin>>H[i];
FOR(i,4) cin>>AH[i];
disjoint_intervals dj;
pr= 0;
ll ret = 1;
for(int i=0;i<n;++i){
int j=i%k;
dj.insert(ii(L[j],L[j]+W[j]),H[j]);
ret = ret * pr % MOD;
upd(j);
}
cout << ret << '\n';
}
int main() {
READ(1);
int T;cin>>T;
for(int tt=1;tt<=T;++tt){
cout << "Case #" << tt << ": ";
docase();
}
return 0;
}
