제출 #1126517

#제출 시각아이디문제언어결과실행 시간메모리
1126517Muhammet나일강 (IOI24_nile)C++20
100 / 100
757 ms99964 KiB
#include <bits/stdc++.h> #include "nile.h" // #include "grader.cpp" using namespace std; #define ll long long #define sz(s) (int)s.size() #define ff first #define ss second ll sp[5][200005][30]; vector <vector <ll>> st; ll f(int x, int y, bool z){ int lg1 = log2(y-x+1); return min(sp[z][x][lg1],sp[z][y-(1LL<<lg1)+1][lg1]); } ll upd(int nd, int l, int r, int ind, bool z, ll vl){ if(l > ind or r < ind) return st[z][nd]; if(l == r) return st[z][nd] = vl; int md = (l + r) / 2; return st[z][nd] = min(upd(nd*2,l,md,ind,z,vl), upd(nd*2+1,md+1,r,ind,z,vl)); } ll fnd(int nd, int l, int r, int x, int y, bool z){ if(l > y or r < x) return 1e18; if(l >= x and r <= y) return st[z][nd]; int md = (l + r) / 2; return min(fnd(nd*2,l,md,x,y,z), fnd(nd*2+1,md+1,r,x,y,z)); } vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){ int q = sz(e), n = sz(a); vector <int> e1 = e; vector <ll> vans; sort(e.begin(), e.end()); ll d = e[0]; vector <pair<ll,pair<ll,ll>>> v; for(int i = 0; i < n; i++){ v.push_back({w[i],{a[i],b[i]}}); } map <pair<int,int>, ll> m; map <int,int> m1; sort(v.begin(), v.end()); ll ans = 0; bool tr = 0; set <int> s; vector <pair<ll,int>> dis, dis1; for(int i = 0; i < n-1; i++){ int ind = i; while(ind < (n-1)){ if(v[ind+1].ff - v[ind].ff > d) break; ind++; } ll k = 0; for(int j = i; j <= ind; j++){ k += (v[j].ss.ss); } ll k2 = k; k = 1e18; if((ind-i) % 2 == 1){ k = k2; } else { for(int j = i; j <= ind; j++){ ll k1 = k2; k1 -= (v[j].ss.ss); k1 += (v[j].ss.ff); if((j-i) % 2 == 0){ k = min(k, k1); } else { if(v[j+1].ff-v[j-1].ff <= d){ k = min(k, k1); } } } k = min(k, k2 + (v[i].ss.ff-v[i].ss.ss)); k = min(k, k2 + (v[ind].ss.ff-v[ind].ss.ss)); } if(ind != n-1){ dis.push_back({v[ind+1].ff-v[ind].ff,ind}); } m[{i,ind}] = k; s.insert(ind); m1[i] = ind; m1[ind] = i; i = ind; ans += k; if(i == n-1) tr = 1; } if(tr == 0){ ans += v[n-1].ss.ff; m[{n-1,n-1}] = v[n-1].ss.ff; m1[n-1] = n-1; s.insert(n-1); } sort(dis.rbegin(), dis.rend()); vector <ll> v1, p(n,0); p[0] = v[0].ss.ss; for(int i = 1; i < n; i++){ p[i] = p[i-1] + v[i].ss.ss; } for(int i = 0; i < 2; i++){ for(int j = 0; j < n; j++){ for(int i1 = 0; i1 < 27; i1++){ sp[i][j][i1] = 1e18; } } } for(int i = 0; i < n; i++){ sp[i%2][i][0] = (v[i].ss.ff-v[i].ss.ss); } for(int j = 1; j < 27; j++){ for(int i = 0; i < n-(1LL<<j)+1; i++){ sp[0][i][j] = min(sp[0][i][j-1],sp[0][i+(1LL<<(j-1))][j-1]); sp[1][i][j] = min(sp[1][i][j-1],sp[1][i+(1LL<<(j-1))][j-1]); } } for(int i = 1; i < n-1; i++){ dis1.push_back({(v[i+1].ff-v[i-1].ff),i}); } sort(dis1.rbegin(), dis1.rend()); st.assign(3, vector <ll> (n*8,1e18)); map <ll,ll> mp; mp[d] = ans; for(int i = 1; i < q; i++){ d = e[i]; while(sz(dis1) > 0){ if(d >= dis1.back().ff){ int x = dis1.back().ss; dis1.pop_back(); upd(1,0,n-1,x,x%2,(v[x].ss.ff-v[x].ss.ss)); int y = *s.lower_bound(x); int y1 = m1[y]; ll z1 = ((y1 != y and (y-y1+1) % 2 == 1) ? fnd(1,0,n-1,y1+1,y-1,1-(y1%2)) : 1e18), z2 = p[y]; if(y1 != 0) z2 -= p[y1-1]; if(z1+z2 < m[{y1,y}]){ ans -= m[{y1,y}]; ans += (z1+z2); m[{y1,y}] = (z1+z2); } } else break; } while(sz(dis) > 0){ if(d >= dis.back().ff){ int x = dis.back().ss; dis.pop_back(); s.erase(s.find(x)); ans -= m[{m1[x],x}]; ans -= m[{x+1,m1[x+1]}]; int a1 = m1[x], b1 = m1[x+1]; m1[a1] = b1; m1[b1] = a1; ll y = p[b1]; if(a1 > 0) y -= p[a1-1]; if((b1-a1) % 2 == 1){ m[{a1,b1}] = y; } else { ll a2 = (f(a1,b1,(a1%2))); if(a1 != b1) a2 = min(a2,fnd(1,0,n-1,a1+1,b1-1,1-(a1%2))); y += a2; m[{a1,b1}] = y; } ans += y; } else break; } mp[d] = ans; } for(auto i : e1){ vans.push_back(mp[i]); } return vans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...