Submission #352736
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() { 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]; 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 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 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 } P[k] = a; Q[k] = b; } 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
Submission Time | |
---|---|
Task | D - 高橋くんとマラソンコース |
User | brly |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 2459 Byte |
Status | AC |
Exec Time | 1566 ms |
Memory | 19600 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 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 | 136 ms | 16424 KB |
subtask1_0.txt | AC | 141 ms | 16420 KB |
subtask1_1.txt | AC | 139 ms | 16424 KB |
subtask1_2.txt | AC | 142 ms | 16416 KB |
subtask1_3.txt | AC | 139 ms | 16424 KB |
subtask1_4.txt | AC | 138 ms | 16420 KB |
subtask1_5.txt | AC | 139 ms | 16420 KB |
subtask1_6.txt | AC | 141 ms | 16428 KB |
subtask1_7.txt | AC | 140 ms | 16416 KB |
subtask1_special.txt | AC | 140 ms | 16420 KB |
subtask1_special2.txt | AC | 137 ms | 16424 KB |
subtask2_0.txt | AC | 1113 ms | 19488 KB |
subtask2_1.txt | AC | 1164 ms | 19504 KB |
subtask2_2.txt | AC | 1113 ms | 19488 KB |
subtask2_3.txt | AC | 1159 ms | 19484 KB |
subtask2_4.txt | AC | 1120 ms | 19488 KB |
subtask2_5.txt | AC | 1126 ms | 19500 KB |
subtask2_6.txt | AC | 1123 ms | 19600 KB |
subtask2_7.txt | AC | 1121 ms | 19488 KB |
subtask2_special.txt | AC | 1566 ms | 19424 KB |
subtask2_special2.txt | AC | 1409 ms | 19484 KB |
subtask2_special3.txt | AC | 719 ms | 19484 KB |