# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
44843 | 2018-04-08T05:01:36 Z | RayaBurong25_1 | Roller Coaster Railroad (IOI16_railroad) | C++17 | 672 ms | 27140 KB |
#include "railroad.h" #include <set> #include <algorithm> #include <stdio.h> std::set<int> EP; std::vector<int> EPc; long long FenR[400005]; long long FenL[400005]; void upR(int p, long long v) { for (; p <= EPc.size(); p += p&-p) FenR[p] += v; } void upL(int p, long long v) { for (; p <= EPc.size(); p += p&-p) FenL[p] += v; } long long queryR(int p) { long long r = 0; for (; p > 0; p -= p&-p) r += FenR[p]; return r; } long long queryL(int p) { long long r = 0; for (; p > 0; p -= p&-p) r += FenL[p]; return r; } long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { int n = (int) s.size(); int i; for (i = 0; i < n; i++) { EP.insert(s[i]); EP.insert(t[i]); } std::set<int>::iterator it; for (it = EP.begin(); it != EP.end(); it++) EPc.push_back(*it); for (i = 0; i < n; i++) { s[i] = std::lower_bound(EPc.begin(), EPc.end(), s[i]) - EPc.begin() + 1; t[i] = std::lower_bound(EPc.begin(), EPc.end(), t[i]) - EPc.begin() + 1; if (s[i] < t[i]) { upR(s[i], 1LL); upR(t[i], -1LL); } else if (s[i] > t[i]) { upL(s[i], 1LL); upL(t[i], -1LL); } } long long ans = 0, r; for (i = 0; i < EPc.size() - 1; i++) { if ((r = queryR(i + 1) - queryL(i + 1)) > 1) { ans += (r - 1)*(EPc[i + 1] - EPc[i]); } // printf("r %lld\n", r); } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 248 KB | answer is not correct: 15509384 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 248 KB | answer is not correct: 15509384 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 672 ms | 27140 KB | answer is not correct: 1 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 248 KB | answer is not correct: 15509384 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |