Submission #352731

---

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 = 0;
  pw[0] = pw[1] = 0;
  for (int i = 1; i <= 2000010; i++)
  {
    pw[i] = log((double)i);
    pw[i] += pw[i-1];
  }

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

    Bit<double> bit(N+1);

    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;
      ptn = pw[absp + absq] - pw[absp] - pw[absq];

      //cout << ptn << endl;

      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;

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

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

        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 = pw[absp + absq] - pw[absp] - pw[absq];
          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 = pw[absp + absq] - pw[absp] - pw[absq];
          bit.add(k, ptn); // 1-th indexed

        }

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

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

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

      }



    }

  }
  return 0;
}

Submission Info

Judge Result