SRM470 Div1 Medium

500
これから引く線同士、既に引かれている線同士、引かれている線と引く線同士の3つに分けて考える。
左右にある空きを前もって数えようと思ったけど、途中で挫折
毎回countを呼んでも間に合うようだった
できてみると簡単だけど、解くまでに相当な時間を使ってしまった

class DrawingLines {
public:
  double countLineCrossings(int n, vector <int> S, vector <int> E) 
  {

    double ret = 0;

    for (int i = 0; i < S.size(); ++i) {
      for (int j = i + 1; j < S.size(); ++j) {
        if (S[i] < S[j] && E[i] < E[j]) continue;
        if (S[i] > S[j] && E[i] > E[j]) continue;
        ret += 1.0;
      }
    }

    int fixed = S.size();
    int free = n - fixed;    
    ret += free * (free - 1) / 2.0 / 2.0;

    int s[n + 1];
    int e[n + 1];
    fill(s, s + n + 1, false);
    fill(e, e + n + 1, false);

    for (int i = 0; i < S.size(); ++i) {
      s[S[i]] = true;
      e[E[i]] = true;
    }

    for (int i = 0; i < S.size(); ++i) {
      double el = count(e + 1, e + E[i], false);
      double er = count(e + E[i], e + n + 1, false);
      double sl = count(s + 1, s + S[i], false);
      double sr = count(s + S[i], s + n + 1, false);
      ret += (sl * er + sr * el) / (double)free;
    }

    

    return ret;

  }