제출 #96872

#제출 시각아이디문제언어결과실행 시간메모리
96872youngyojunRoller Coaster Railroad (IOI16_railroad)C++11
30 / 100
358 ms17056 KiB
#include "railroad.h" #include <bits/stdc++.h> #define eb emplace_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define sorv(V) sort(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define INF (0x3f3f3f3f) using namespace std; typedef long long ll; const int MAXN = 200055; int ud[MAXN*2], C[MAXN*2], O[MAXN*2]; vector<int> XV; int A[MAXN], B[MAXN], AI[MAXN], BI[MAXN]; ll Ans; int N, K; int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); } void uf(int a, int b) { ud[uf(b)] = uf(a); } ll getAns() { XV.eb(0); XV.eb(INF); for(int i = 0; i < N; i++) { XV.eb(A[i]); XV.eb(B[i]); } sorv(XV); univ(XV); K = sz(XV); iota(ud, ud+K, 0); for(int i = 0; i < N; i++) { AI[i] = int(lower_bound(allv(XV), A[i]) - XV.begin()); BI[i] = int(lower_bound(allv(XV), B[i]) - XV.begin()); C[AI[i]]--; C[BI[i]]++; uf(AI[i], BI[i]); } C[0] = -1; C[1]++; uf(0, 1); for(int i = 2; i < K; i++) if(C[i-1]) { uf(i-1, i); if(C[i-1] < 0) Ans -= C[i-1]; C[i] += C[i-1]; C[i-1] = 0; } iota(O, O+K, 0); sort(O+1, O+K, [&](int a, int b) { return XV[a]-XV[a-1] < XV[b]-XV[b-1]; }); for(int oi = 1, i; oi < K; oi++) { i = O[oi]; if(uf(i-1) == uf(i)) continue; Ans += XV[i] - XV[i-1]; uf(i-1, i); } return Ans; } long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { ::N = sz(s); for(int i = 0; i < N; i++) { ::A[i] = s[i]; ::B[i] = t[i]; } return getAns(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...