Submission #352685
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; if (absp && absq) ptn = (pw[absp + absq]) - (pw[absp]) - (pw[absq]); else ptn = log2(1.0); //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; 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 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 | 2770 Byte |
Status | WA |
Exec Time | 1485 ms |
Memory | 19616 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 70 | ||||||||||
Status |
|
|
|
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 | 138 ms | 16424 KB |
subtask0_sample_02.txt | AC | 136 ms | 16416 KB |
subtask1_0.txt | WA | 141 ms | 16428 KB |
subtask1_1.txt | WA | 143 ms | 16396 KB |
subtask1_2.txt | WA | 141 ms | 16412 KB |
subtask1_3.txt | WA | 142 ms | 16424 KB |
subtask1_4.txt | WA | 140 ms | 16416 KB |
subtask1_5.txt | WA | 141 ms | 16420 KB |
subtask1_6.txt | WA | 141 ms | 16372 KB |
subtask1_7.txt | WA | 141 ms | 16424 KB |
subtask1_special.txt | AC | 143 ms | 16420 KB |
subtask1_special2.txt | AC | 140 ms | 16424 KB |
subtask2_0.txt | WA | 1132 ms | 19492 KB |
subtask2_1.txt | WA | 1136 ms | 19432 KB |
subtask2_2.txt | WA | 1135 ms | 19488 KB |
subtask2_3.txt | WA | 1135 ms | 19496 KB |
subtask2_4.txt | WA | 1137 ms | 19488 KB |
subtask2_5.txt | WA | 1157 ms | 19616 KB |
subtask2_6.txt | WA | 1142 ms | 19496 KB |
subtask2_7.txt | WA | 1126 ms | 19500 KB |
subtask2_special.txt | AC | 1485 ms | 19488 KB |
subtask2_special2.txt | AC | 1443 ms | 19492 KB |
subtask2_special3.txt | AC | 694 ms | 19488 KB |