제출 #846269

#제출 시각아이디문제언어결과실행 시간메모리
846269denniskim추월 (IOI23_overtaking)C++17
65 / 100
3519 ms57920 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) ll n, x, m; ll t[1010]; ll w[1010]; ll cc; pll a[1010][1010]; ll tmp[1010]; ll TM[1010][1010]; ll s[1010]; vector<pll> vv[1010]; void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) { n = N; x = X; m = M; for(ll i = 0 ; i < n ; i++) { if(W[i] <= X) continue; t[cc] = T[i]; w[cc++] = W[i]; } for(ll i = 0 ; i < m ; i++) s[i] = S[i]; n = cc; for(ll i = 0 ; i < n ; i++) a[0][i] = {t[i], w[i]}; sort(a[0], a[0] + n); for(ll i = 0 ; i < m - 1 ; i++) { vector<pll> vec, evec; vector<ll> vec2; ll dist = s[i + 1] - s[i]; for(ll j = 0 ; j < n ; j++) { ll TT = a[i][j].fi; ll WW = a[i][j].se; TM[i][j] = TT + WW * dist; vec.push_back({TT + 1, j}); evec.push_back({TT + (WW - x) * dist, j}); vec2.push_back(TT + 1); vec2.push_back(TT + (WW - x) * dist); } vec2.push_back(0); sort(vec.begin(), vec.end()); sort(evec.begin(), evec.end()); compress(vec2); multiset<ll> st; ll p1 = 0, p2 = 0; for(auto &j : vec2) { while(p1 < (ll)vec.size() && vec[p1].fi <= j) { st.insert(TM[i][vec[p1].se]); p1++; } while(p2 < (ll)evec.size() && evec[p2].fi <= j) { st.erase(st.find(TM[i][evec[p2].se])); p2++; } if(!st.empty()) vv[i].push_back({j, (*st.rbegin())}); else vv[i].push_back({j, -1}); } stack<pll> stk; for(ll j = n - 1 ; j >= 0 ; j--) { while(!stk.empty() && stk.top().fi <= TM[i][j]) stk.pop(); stk.push({TM[i][j], j}); } vector<ll> idx; while(!stk.empty()) { idx.push_back(stk.top().se); stk.pop(); } idx.push_back(n); for(ll j = 0 ; j < (ll)idx.size() - 1 ; j++) { for(ll k = idx[j] ; k < idx[j + 1] ; k++) tmp[k] = TM[i][idx[j]]; } for(ll j = 0 ; j < n ; j++) a[i + 1][j] = {tmp[j], a[i][j].se}; sort(a[i + 1], a[i + 1] + n); } } ll arrival_time(ll Y) { ll ret = Y; for(ll i = 0 ; i < m - 1 ; i++) { ll l = 0, r = (ll)vv[i].size() - 1; while(l <= r) { ll mid = (l + r) >> 1; if(vv[i][mid].fi <= ret) l = mid + 1; else r = mid - 1; } if(vv[i][r].se == -1) ret += (s[i + 1] - s[i]) * x; else ret = vv[i][r].se; } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...