제출 #134637

#제출 시각아이디문제언어결과실행 시간메모리
134637Mahdi_JfriRoller Coaster Railroad (IOI16_railroad)C++14
0 / 100
231 ms10208 KiB
#include "railroad.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 2e5 + 20; int s[maxn] , t[maxn] , n , ind[maxn]; pair<int , int> mn[maxn * 4]; bool cmps(int a , int b) { return s[a] < s[b]; } void build(int s = 0 , int e = n , int v = 1) { if(e - s < 2) { mn[v] = {t[s] , s}; return; } int m = (s + e) / 2; build(s , m , 2 * v); build(m , e , 2 * v + 1); mn[v] = min(mn[2 * v] , mn[2 * v + 1]); } void rem(int p , int s = 0 , int e = n , int v = 1) { if(e - s < 2) { mn[v] = {2e9 , -1}; return; } int m = (s + e) / 2; if(p < m) rem(p , s , m , 2 * v); else rem(p , m , e , 2 * v + 1); mn[v] = min(mn[2 * v] , mn[2 * v + 1]); } pair<int , int> get(int l , int r , int s = 0 , int e = n , int v = 1) { if(l <= s && e <= r) return mn[v]; if(r <= s || e <= l) return make_pair(2e9 , -1); int m = (s + e) / 2; return min(get(l , r , s , m , 2 * v) , get(l , r , m , e , 2 * v + 1)); } long long plan_roller_coaster(vector<int> S, vector<int> T) { n = (int)S.size(); for(int i = 0; i < n; i++) s[i] = S[i] , t[i] = T[i] , ind[i] = i; sort(ind , ind + n , cmps); for(int i = 0; i < n; i++) s[i] = S[ind[i]] , t[i] = T[ind[i]]; build(); int val = 1; for(int _ = 0; _ < n; _++) { int k = lower_bound(s , s + n , val) - s; auto tmp = get(k , n); k = tmp.second , val = tmp.first; if(k < 0) return 1; rem(k); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...