Submission #352693


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

          P[k] = a;
          Q[k] = b;

          absp = abs(a - P[k+1]), absq = abs(b - Q[k+1]);
          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;

          absp = abs(P[k-1] - a), absq = abs(Q[k-1] - b);
          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 lhs = 0, rhs = 0;

        if (r1-l1==1)
        {
          lhs = bit.query(l1) - bit.query(l1-1);
        }
        else
        {
          lhs = bit.query(r1-1) - bit.query(l1-1);
        }

        if (r2-l2==1)
        {
          rhs = bit.query(l2) - bit.query(l2-1);
        }
        else
        {
          rhs = bit.query(r2-1) - bit.query(l2-1);
        }

        // cout << "lhs:" << lhs << endl;
        // cout << "rhs:" << rhs << endl;

        // 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", lhs > rhs ? "FIRST" : "SECOND");

      }



    }

  }
  return 0;
}

Submission Info

Submission Time
Task D - 高橋くんとマラソンコース
User brly
Language C++11 (GCC 4.9.2)
Score 0
Code Size 3022 Byte
Status WA
Exec Time 1511 ms
Memory 19496 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 2
AC × 4
WA × 8
AC × 7
WA × 16
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
Subtask1 subtask1_0.txt, subtask1_1.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_special.txt, subtask1_special2.txt, subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_0.txt, subtask1_1.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_special.txt, subtask1_special2.txt, subtask2_0.txt, subtask2_1.txt, subtask2_2.txt, subtask2_3.txt, subtask2_4.txt, subtask2_5.txt, subtask2_6.txt, subtask2_7.txt, subtask2_special.txt, subtask2_special2.txt, subtask2_special3.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 137 ms 16416 KB
subtask0_sample_02.txt AC 135 ms 16348 KB
subtask1_0.txt WA 144 ms 16424 KB
subtask1_1.txt WA 141 ms 16428 KB
subtask1_2.txt WA 140 ms 16412 KB
subtask1_3.txt WA 140 ms 16424 KB
subtask1_4.txt WA 141 ms 16424 KB
subtask1_5.txt WA 141 ms 16368 KB
subtask1_6.txt WA 138 ms 16352 KB
subtask1_7.txt WA 143 ms 16420 KB
subtask1_special.txt AC 142 ms 16416 KB
subtask1_special2.txt AC 138 ms 16416 KB
subtask2_0.txt WA 1141 ms 19436 KB
subtask2_1.txt WA 1097 ms 19484 KB
subtask2_2.txt WA 1144 ms 19488 KB
subtask2_3.txt WA 1135 ms 19436 KB
subtask2_4.txt WA 1174 ms 19488 KB
subtask2_5.txt WA 1145 ms 19492 KB
subtask2_6.txt WA 1128 ms 19488 KB
subtask2_7.txt WA 1145 ms 19496 KB
subtask2_special.txt AC 1511 ms 19488 KB
subtask2_special2.txt AC 1491 ms 19492 KB
subtask2_special3.txt AC 700 ms 19492 KB