cafelier@SRM

Codeforces 107 Div1 C

あとで | 12:12 |

• 最終的には、書いてみるとすごく普通だった。
• セグメント木、区間に対する効率の良いupdateが可能なパターン(まとめて正負反転とか)まで込みでどうライブラリ化すると綺麗になるか考えきれないでいる（今回の問題には関係ないですが）

template<typename Node>
class SegmentTree
{
public:
   template<typename Seq>
   SegmentTree(const Seq& s) {
      int N = 1;
      while( N < s.size() )
         N <<= 1;

      tree.resize(tree.size()+1); tree.back().resize(N);
      for(int i=0; i<N; ++i)
         tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Zero();

      while(N>>=1) {
         tree.resize(tree.size()+1); tree.back().resize(N);
         for(int i=0; i<N; ++i)
            CalcMidNode(tree.size()-1, i);
      }
   }

   Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
      return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
   }
/*
   template<typename Value>
   void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n・|e-s|)
      SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
   }
*/
private:
   void CalcMidNode(int lv, int idx)
   {
      tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
   }

   Node QueryRec(int s, int e, int lv, int idx, int stride)
   {
      const int myL = stride*idx;
      const int myR = stride*(idx+1);
      if( e<=myL || myR<=s )
         return Node::Zero();
      if( s<=myL && myR<=e )
         return tree[lv][idx];
      return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
                          QueryRec(s,e,lv-1,idx*2+1,stride/2));
   }
/*
   void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
   {
      const int myL = stride*idx;
      const int myR = stride*(idx+1);
      if( e<=myL || myR<=s )
         return;
      if( stride == 1 ) {
         tree[lv][idx] = n;
      } else {
         SetRec(s,e,n,lv-1,idx*2,stride/2);
         SetRec(s,e,n,lv-1,idx*2+1,stride/2);
         CalcMidNode(lv, idx);
      }
   }
*/
   vector< vector<Node> > tree;
};

// Any homomorphism from the original array structure can be used as segtree nodes.
struct Node
{
   double sum;
   double maxLeft;
   double maxRight;
   double maxSum;
   static Node Zero()
   {
      Node c = {0, 0, 0, 0};
      return c;
   }
   static Node One(double v)
   {
      Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
      return c;
   }
   static Node Concat(const Node& l, const Node& r)
   {
      Node c = {
         l.sum + r.sum,
         max(l.maxLeft, l.sum+r.maxLeft),
         max(l.maxRight+r.sum, r.maxRight),
         max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
      };
      return c;
   }
};

//---------------------------------------------------------

double solve(
   const vector<int>& X,
   const vector<int>& P,
   const vector< pair<int,int> >& AB,
   int C
){
   vector<double> gain(X.size()-1);
   for(int i=0; i<gain.size(); ++i)
      gain[i] = (X[i+1]-X[i])/2.0 - C/100.0*P[i];

   SegmentTree<Node> st(gain);

   double total = 0.0;
   for(int i=0; i<AB.size(); ++i)
      total += st.Query(AB[i].first, AB[i].second).maxSum;
   return total;
}

int main()
{
   for(int N,M,C; cin>>N>>M>>C; )
   {
      vector<int> X(N);
      for(int i=0; i<N; ++i) cin >> X[i];
      vector<int> P(N-1);
      for(int i=0; i<N-1; ++i) cin >> P[i];
      vector< pair<int,int> > AB(M);
      for(int i=0; i<M; ++i) {cin >> AB[i].first >> AB[i].second; AB[i].first--; AB[i].second--;}

      cout << setiosflags(ios::fixed) << setprecision(9) << solve(X, P, AB, C) << endl;
   }
}