Submission #352648

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N;
int P[300000], Q[300000];

template <class T>
struct Bit
{
  const int N;
  vector<T> d;

  Bit(const int n) : N(n+2), d(n+4) {}

  void add(int index, T value)
  {
    for (int i = index; i <= N; i += i & -i) //
    {
      d[i] += value;
    }
  }

  T query(const int index)
  {
    T ret = 0;
    for (int i = index; i > 0; i -= i & -i) //
    {
      ret += d[i];
    }
    return ret;
  }
};


double pw[2000100];

int main()
{
  double cur = 1;
  for (int i = 1; i <= 2000010; i++)
  {
    cur = cur + log(i);
    pw[i] = cur;
  }

  while (cin >> N)
  {
    for (int i = 0; i < N; i++)
    {
      cin>>P[i]>>Q[i];
    }

    Bit<double> bit(N);

    for (int i = 0; i < N-1; i++)
    {
      int p0 = P[i], q0 = Q[i];
      int p1 = P[i+1], q1 = Q[i+1];

      int absp = abs(p0 - p1), absq = abs(q0 - q1);
      double ptn = 0;
      if (absp && absq)
        ptn = (pw[absp + absq]) / (pw[absp]) / (pw[absq]);
      else
        ptn = log(1);

      bit.add(i+1, ptn); // 1-th indexed
    }

    int Q_;
    cin>>Q_;

    while (Q_--)
    {
      int t;
      cin>>t;
      if (t==1)
      {
        int k, a, b;
        cin>>k>>a>>b;
        --k;
        P[k] = a;
        Q[k] = b;

        if (k != N-1)
        {
          int absp = abs(a - P[k+1]), absq = abs(b - Q[k+1]);
          double ptn = (absp && absq) ? (pw[absp + absq] / pw[absp] / pw[absq]) : log(1) ;
          bit.add(k+1, ptn); // 1-th indexed
        }

        if (k != 0)
        {
          int absp = abs(P[k-1] - a), absq = abs(Q[k-1] - b);
          double ptn = (absp && absq) ? (pw[absp + absq] / pw[absp] / pw[absq]) : log(1) ;
          bit.add(k, ptn); // 1-th indexed
        }

      }
      else
      {
        int l1, r1, l2, r2;
        cin>>l1>>r1>>l2>>r2;

        double to_l1 = bit.query(l1);
        double to_r1 = bit.query(r1);
        double to_l2 = bit.query(l2);
        double to_r2 = bit.query(r2);

        printf("%s\n", (to_r1 - to_l1) > (to_r2 - to_l2) ? "FIRST" : "SECOND");

      }
    }
  }
  return 0;
}

Submission Info

Judge Result