제출 #1193720

#제출 시각아이디문제언어결과실행 시간메모리
1193720Zbyszek99추월 (IOI23_overtaking)C++20
0 / 100
1 ms836 KiB
#include "overtaking.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct frac { __int128_t a,b; frac operator+(const frac& other)const { __int128_t a2 = a*other.b + other.a*b; __int128_t b2 = b*other.b; __int128_t g = __gcd(a2,b2); return {a2/g,b2/g}; } frac operator-(const frac& other) const { __int128_t a2 = a*other.b - other.a*b; __int128_t b2 = b*other.b; __int128_t g = __gcd(a2,b2); return {a2/g,b2/g}; } frac operator*(const frac& other) const { __int128_t a2 = a*other.a; __int128_t b2 = b*other.b; __int128_t g = __gcd(a2,b2); return {a2/g,b2/g}; } frac operator/(const frac& other) const { __int128_t a2 = a*other.b; __int128_t b2 = b*other.a; __int128_t g = __gcd(a2,b2); return {a2/g,b2/g}; } bool operator<(const frac& other) const { return a*other.b < other.a*b; } bool operator<=(const frac& other) { return a*other.b <= other.a*b; } bool operator>(const frac& other) { return a*other.b > other.a*b; } bool operator>=(const frac& other) { return a*other.b >= other.a*b; } }; ll L; int n,m; ll T[1001]; ll W[1001]; ll S[1001]; ll arr_time[1001][1001]; set<pll> end_sets[1001]; ll X; void init(int L2, int N2, vl T2, vi W2, int X2, int M2, vi S2) { L = L2; n = N2; rep(i,n) T[i] = T2[i]; rep(i,n) W[i] = W2[i]; X = X2; m = M2; rep(i,m) S[i] = S2[i]; vector<pll> bus; rep(i,n) bus.pb({W[i],T[i]}); sort(all(bus)); reverse(all(bus)); n = 0; forall(it,bus) { if(it.ff <= X) break; W[n] = it.ff; T[n] = it.ss; n++; } rep(i,n) { ll time_ = T[i]; rep(j,m-1) { arr_time[i][j] = time_; auto nxt = end_sets[j].lower_bound({time_,-1e18}); if(nxt == end_sets[j].begin()) { time_ += W[i] * (S[j+1] - S[j]); continue; } nxt--; if((*nxt).ss >= time_ + W[i]*(S[j+1]-S[j])) { time_ = (*nxt).ss; } else { time_ += W[i] * (S[j+1] - S[j]); } } arr_time[i][m-1] = time_; rep(j,m-1) { auto nxt = end_sets[j].lower_bound({arr_time[i][j]+1,-1e18}); if(nxt == end_sets[j].begin()) { end_sets[j].insert({arr_time[i][j],arr_time[i][j+1]}); continue; } nxt--; if((*nxt).ss >= arr_time[i][j+1]) continue; while(true) { auto it = end_sets[j].lower_bound({arr_time[i][j],-1e18}); if(it == end_sets[j].begin()) break; it--; if((*it).ss <= arr_time[i][j+1]) { end_sets[j].erase(it); } else break; } end_sets[j].insert({arr_time[i][j],arr_time[i][j+1]}); } } return; } ll arrival_time(ll time_) { int cur_stop = 0; while(cur_stop != m-1) { pair<frac,int> com = {{(ll)1e18,1},-1}; rep(i,n) { frac oneX = {time_,X}; frac oneW = {arr_time[i][cur_stop],W[i]}; frac s1 = {S[cur_stop],1}; frac c = ((frac){time_*W[i],1}-(frac){arr_time[i][cur_stop]*X,1}) / (frac){W[i]-X,1}; // cerr << i << " " << (ll)c.a << "/" << (ll)c.b << " " << arr_time[i][cur_stop] << " " << W[i] << " xd\n"; if(c > (frac){time_,1}) { com = min(com,{c,i}); } } // cerr <<cur_stop << " " << time_ << " " << com.ff.a << "/" << com.ff.b << " " << com.ss << " com\n"; if(com.ss == -1) { time_ += (S[m-1] - S[cur_stop]) * X; return time_; } frac poz = (com.ff - (frac){time_,1}) * (frac){1,X} + (frac){S[cur_stop],1}; // cerr << poz.a << " " << poz.b << " poz\n"; int l = cur_stop; int r = m-1; int ans = -1; while(l <= r) { int mid = (l+r)/2; // cerr << mid << " " << S[mid] << " bin\n"; if((frac){S[mid],1} < poz) { ans = mid; l = mid+1; } else { r = mid-1; } } // cerr << ans << " ans\n"; if(ans == m-1) { time_ += (S[m-1] - S[cur_stop]) * X; return time_; } time_ = arr_time[com.ss][ans+1]; cur_stop = ans+1; } return time_; }
#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...