621C - Wet Shark and Flowers - CodeForces Solution

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr)
#define lp(i,n) for(int i = 0; i < n; i++)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define invrep(i,a,b) for(int i = a; i >= b; i--)
#define PB(a) push_back(a)
#define MP make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define line cout<<endl
#define EPS 0.0000000001
#define PI 3.14159265358979323846
#define DEC greater<int>()
#define X real()
#define Y imag()
using namespace std;
typedef complex<long double> P;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<ii> vii;
ll sum_vector(vi v){ll s = 0;for(auto x:v)s+=(ll)x;return s;}
vl cum_vector(vi v){int n = sz(v);vl cum(n);cum[0] = v[0];rep(i,1,n-1)cum[i] =(ll) v[i] + cum[i-1];return cum;}
void eyle(bool value){cout<<(value?"YES":"NO")<<"\n";}
vi in(int n){vi v(n);lp(i,n)cin>>v[i];return v;}
template <typename T>void out(vector<T> v){for(auto x:v)cout << x << " ";line;}
bool is_integer(double x){return floor(x) == ceil(x);}
ll sum_n(ll n){return (ll)n*(n+1)/2;}
double my_log(int base, ll N){return (double)log(N)/log(base);}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll gcd(vi v){ll g = v[0];rep(i,1,sz(v)-1)g = gcd(g,v[i]);return g;}
ll lcm(int a,int b){return (ll)a*b / gcd(a,b);}
ll lcm(vi v){ll ans = v[0];rep(i,1,sz(v)-1)ans = ((ll)((v[i]*ans))/(gcd(v[i],ans)));return ans;}
//choose k from n:
ll C_kn(ll k, ll n){ll res = 1;if(k>n-k)k=n-k;for(ll i=0;i<k;++i){res*=(n-i);res/=(i+1);}return res;}
int ctoi(char c){return c-'0';}
int long_double_to_int(long double x){if(fabs(x-ceil(x)) <= EPS)return ceil(x);return floor(x);}
/* custom sort functions */
bool sort_dec_pair(const pair<int,int> &a,const pair<int,int> &b){
    return a.first > b.first;
}
bool costum(const pair<int,int> &a,const pair<int,int> &b){
    if (a.F != b.F)return a.F < b.F;
    return a.S > b.S;
}
int compare_double(long double a,long double b){return fabs(a-b)<=EPS?0:a-b>0?1:2;}
const int INF = INT_MAX;
ll MOD = 2000000;
const int N = 100000;
long double prob(long double l, long double r, long double p, char c){
    long double cnt = floor(r/p) - floor((l-1)/p);
    long double res = cnt / (r-l+1.0);
    return c=='1'?res:1.0-res;
}
void solve(){
    int n, p;
    cin >> n >> p;
    vi l(n+2), r(n+2);
    lp(i,n)cin >> l[i+1] >> r[i+1];
    l[0] = l[n];
    r[0] = r[n];
    l[n+1] = l[1];
    r[n+1] = r[1];
    vector<string> config;
    lp(i,2){
        lp(j,2){
            lp(k,2){
                string s;
                s.push_back(char('0'+i));
                s.push_back(char('0'+j));
                s.push_back(char('0'+k));
                config.push_back(s);
            }
        }
    }
    long double x = 0.0;
    rep(i,1,n){
        for(auto c: config){
            long double cur_prob = 1.0;
            long double cur_val = 1000*(max(c[1], c[0])=='1') + 1000*(max(c[1], c[2])=='1');
            lp(j,3)cur_prob*=prob(l[i-1+j], r[i-1+j], p, c[j]);
            x+=cur_prob*cur_val;
        }
    }
    cout.precision(15);
    cout << x << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    fast;
    int t = 1;
  //  cin>>t;
    while(t--)solve();
    return 0;
}