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 |
|
|
|
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 |