結果
| 問題 |
No.1467 Selling Cars
|
| コンテスト | |
| ユーザー |
 Taiki0715
|
| 提出日時 | 2025-05-28 22:40:20 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 21,137 bytes |
| コンパイル時間 | 4,501 ms |
| コンパイル使用メモリ | 309,104 KB |
| 実行使用メモリ | 16,068 KB |
| 最終ジャッジ日時 | 2025-05-28 22:40:44 |
| 合計ジャッジ時間 | 22,870 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | AC * 1 TLE * 3 -- * 27 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
clock_t start;
Timer(){
start=clock();
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout<<fixed<<setprecision(16);
}
inline double now(){return (double)(clock()-start)/1000;}
#ifdef LOCAL
~Timer(){
cerr<<"time:";
cerr<<now();
cerr<<"ms\n";
}
#endif
}timer;
void SOLVE();
int main(){
int testcase=1;
//cin>>testcase;
for(int i=0;i<testcase;i++){
SOLVE();
}
}
#include<type_traits>
struct has_update_impl{
template<typename T>
static auto check(T&&x)->decltype(x.update(),std::true_type{});
template<typename T>
static auto check(...)->std::false_type;
};
template<typename T>
struct has_update:public decltype(has_update_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_update_v=has_update<T>::value;
struct has_push_impl{
template<typename T>
static auto check(T&&x)->decltype(x.push(),std::true_type{});
template<typename T>
static auto check(...)->std::false_type;
};
template<typename T>
struct has_push:public decltype(has_push_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_push_v=has_push<T>::value;
struct has_middle_impl{
template<typename T>
static auto check(T&&x)->decltype(x.middle,std::true_type{});
template<typename T>
static auto check(...)->std::false_type;
};
template<typename T>
struct has_middle:public decltype(has_middle_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_middle_v=has_middle<T>::value;
template<typename T,bool no_push=false>
void splay(T*nd){
if constexpr(has_push_v<T>&&!no_push)nd->push();
while(nd->par){
T *p=nd->par;
T *pp=p->par;
if constexpr(has_push_v<T>&&!no_push){
if(pp)pp->push();
p->push();
nd->push();
}
if(p->left==nd){
if(pp){
if(pp->left==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
pp->left=p->right;
if(pp->left)pp->left->par=pp;
p->left=nd->right;
if(p->left)p->left->par=p;
nd->right=p;
p->par=nd;
p->right=pp;
pp->par=p;
if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
continue;
}
else if(pp->right==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
p->left=nd->right;
if(p->left)p->left->par=p;
pp->right=nd->left;
if(pp->right)pp->right->par=pp;
nd->left=pp;
pp->par=nd;
nd->right=p;
p->par=nd;
if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
continue;
}
}
nd->par=pp;
if(pp){
if constexpr(has_middle_v<T>){
if(pp->middle==p)pp->middle=nd;
else if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
else{
if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
}
p->left=nd->right;
if(p->left)p->left->par=p;
nd->right=p;
p->par=nd;
if constexpr(has_update_v<T>)p->update(),nd->update();
break;
}
else if(p->right==nd){
if(pp){
if(pp->left==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
p->right=nd->left;
if(p->right)p->right->par=p;
pp->left=nd->right;
if(pp->left)pp->left->par=pp;
nd->left=p;
p->par=nd;
nd->right=pp;
pp->par=nd;
if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
continue;
}
else if(pp->right==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
pp->right=p->left;
if(pp->right)pp->right->par=pp;
p->right=nd->left;
if(p->right)p->right->par=p;
nd->left=p;
p->par=nd;
p->left=pp;
pp->par=p;
if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
continue;
}
}
nd->par=pp;
if(pp){
if constexpr(has_middle_v<T>){
if(pp->middle==p)pp->middle=nd;
else if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
else{
if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
}
p->right=nd->left;
if(p->right)p->right->par=p;
nd->left=p;
p->par=nd;
if constexpr(has_update_v<T>)p->update(),nd->update();
break;
}
else break;
}
}
template<typename T>
[[nodiscard]]T* near(T *nd,decltype(T::key)k){
while(true){
if(k<nd->key){
if constexpr(has_push_v<T>)nd->push();
if(nd->left)nd=nd->left;
else{
splay<T,true>(nd);
return nd;
}
}
else if(nd->key<k){
if constexpr(has_push_v<T>)nd->push();
if(nd->right)nd=nd->right;
else{
splay<T,true>(nd);
return nd;
}
}
else{
splay<T,true>(nd);
return nd;
}
}
return nullptr;
}
template<typename T>
[[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){
while(true){
if constexpr(has_push_v<T>)nd->push();
decltype(T::sz) lsz=nd->left?nd->left->sz:0;
if(lsz==k)break;
else if(k<lsz)nd=nd->left;
else{
nd=nd->right;
k-=1+lsz;
}
}
splay<T,true>(nd);
return nd;
}
template<typename T>
[[nodiscard]]T* merge(T* l,T *r){
if(!l)return r;
if(!r)return l;
while(r->left){
if constexpr(has_push_v<T>)r->push();
r=r->left;
}
if constexpr(has_push_v<T>)r->push();
splay<T,true>(r);
r->left=l;
l->par=r;
if constexpr(has_update_v<T>)r->update();
return r;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* left_most(T*nd){
T nil;
T *rnd=&nil;
while(nd->left){
if constexpr(has_push_v<T>)nd->push();
T *c=nd->left;
if(!c->left){
rnd->left=nd;
if constexpr(has_update_v<T>)nd->par=rnd;
rnd=rnd->left;
nd=c;
}
else{
if constexpr(has_push_v<T>)c->push();
nd->left=c->right;
c->right=nd;
if constexpr(has_update_v<T>&&correct_parent){
if(nd->left)nd->left->par=nd;
nd->par=c;
}
if constexpr(has_update_v<T>){
nd->update();
c->par=rnd;
}
rnd->left=c;
nd=c->left;
rnd=rnd->left;
}
}
if constexpr(has_push_v<T>)nd->push();
rnd->left=nd->right;
nd->right=nil.left;
nil.left=nil.right=nullptr;
if constexpr(has_update_v<T>&&correct_parent){
if(rnd->left)rnd->left->par=rnd;
if(nd->right)nd->right->par=nd;
nd->par=nullptr;
}
if constexpr(has_update_v<T>){
while(rnd){
rnd->update();
rnd=rnd->par;
}
}
return nd;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* right_most(T*nd){
T nil;
T *lnd=&nil;
while(nd->right){
if constexpr(has_push_v<T>)nd->push();
T *c=nd->right;
if(!c->right){
lnd->right=nd;
if constexpr(has_update_v<T>)nd->par=lnd;
lnd=lnd->right;
nd=c;
}
else{
if constexpr(has_push_v<T>)c->push();
nd->right=c->left;
c->left=nd;
if constexpr(has_update_v<T>&&correct_parent){
if(nd->right)nd->right->par=nd;
nd->par=c;
}
if constexpr(has_update_v<T>){
nd->update();
c->par=lnd;
}
lnd->right=c;
nd=c->right;
lnd=lnd->right;
}
}
if constexpr(has_push_v<T>)nd->push();
lnd->right=nd->left;
nd->left=nil.right;
nil.left=nil.right=nullptr;
if constexpr(has_update_v<T>&&correct_parent){
if(lnd->right)lnd->right->par=lnd;
if(nd->left)nd->left->par=nd;
nd->par=nullptr;
}
if constexpr(has_update_v<T>){
while(lnd){
lnd->update();
lnd=lnd->par;
}
}
return nd;
}
template<typename T,T limit>
struct SlopeTrick{
private:
static_assert(std::is_integral_v<T>);
static_assert(limit>0);
struct node{
node *left,*right,*par;
T pos,slope,len;
T posr,slope_sum,len_sum;
T lazy,p_add;
node():left(nullptr),right(nullptr),par(nullptr),pos(0),slope(0),len(0),posr(0),slope_sum(0),len_sum(0),lazy(0),p_add(0){}
void propagate(T f,T g){
lazy+=f;
p_add+=g;
slope+=f;
slope_sum+=f*len_sum;
pos+=g;
posr+=g;
}
void push(){
if(left)left->propagate(lazy,p_add);
if(right)right->propagate(lazy,p_add);
lazy=0;
p_add=0;
}
void update(){
posr=pos;
slope_sum=slope*len;
len_sum=len;
if(left){
slope_sum+=left->slope_sum;
len_sum+=left->len_sum;
}
if(right){
posr=right->posr;
slope_sum+=right->slope_sum;
len_sum+=right->len_sum;
}
}
~node(){
if(left)delete left;
if(right)delete right;
}
};
void search_slope(T slope){
while(true){
root->push();
if(root->slope==slope)break;
else if(root->slope>slope){
if(root->left)root=root->left;
else break;
}
else{
if(root->right)root=root->right;
else break;
}
}
splay<node,true>(root);
}
std::pair<node*,node*>split(node *nd,T pos,T l=-limit){
while(true){
nd->push();
T pl=l;
if(nd->left)l=nd->left->posr;
if(l<pos&&pos<=nd->pos){
splay(nd);
if(pos==nd->pos){
node *rnd=nd->right;
nd->right=nullptr;
rnd->par=nullptr;
nd->update();
return std::make_pair(nd,rnd);
}
else{
node *lnd=new node();
lnd->slope=nd->slope;
lnd->pos=pos;
lnd->len=pos-l;
lnd->left=nd->left;
if(lnd->left)lnd->left->par=lnd;
lnd->update();
nd->left=nullptr;
nd->len=nd->pos-pos;
nd->update();
return std::make_pair(lnd,nd);
}
}
else if(pos<nd->pos)l=pl,nd=nd->left;
else l=nd->pos,nd=nd->right;
}
__builtin_unreachable();
}
node *root;
T lv;
public:
SlopeTrick():root(new node()),lv(0){
root->pos=root->posr=limit;
root->len=root->len_sum=limit*2;
}
void add(T b){lv+=b;}
void add_abs(T a,T c=1){
lv+=c*(a-(-limit));
root->propagate(-c,0);
add_r(a,c*2);
}
void add_l(T a,T c=1){
lv+=c*(a-(-limit));
root->propagate(-c,0);
add_r(a,c);
}
void add_r(T a,T c=1){
node *nd=root;
while(true){
nd->push();
if(a<nd->pos){
if(nd->left&&a<nd->left->posr)nd=nd->left;
else break;
}
else{
if(nd->right)nd=nd->right;
else break;
}
}
splay<node,true>(nd);
T l=nd->left?nd->left->posr:-limit;
T r=nd->pos;
if(l==a){
node *l_tmp=nd->left;
nd->left=nullptr;
nd->propagate(c,0);
nd->push();
nd->left=l_tmp;
nd->update();
root=nd;
}
else{
node *lnd=new node();
lnd->left=nd->left;
if(lnd->left)lnd->left->par=lnd;
lnd->pos=a;
lnd->len=a-l;
lnd->slope=nd->slope;
lnd->update();
nd->left=nullptr;
nd->len=r-a;
nd->update();
nd->propagate(c,0);
nd->push();
nd->left=lnd;
lnd->par=nd;
nd->update();
root=nd;
}
}
void add(SlopeTrick rhs){
node *top=nullptr;
T l=-limit;
auto dfs=[&](auto self,node *nd)->void {
if(!nd)return;
nd->push();
self(self,nd->left);
if(top)top->push();
if(nd->pos==limit){
root->propagate(nd->slope,0);
if(top)top->right=root;
root->par=top;
}
else{
auto [left,right]=split(root,nd->pos,l);
left->propagate(nd->slope,0);
if(top)top->right=left;
left->par=top;
top=left;
root=right;
l=top->posr;
}
self(self,nd->right);
};
dfs(dfs,rhs.root);
while(root->par){
root=root->par;
root->update();
}
lv+=rhs.lv;
}
T convolution_l(T c){
root=left_most(root);
if(root->slope>=-c)return -limit;
while(root->slope<-c){
root->push();
lv+=(c+root->slope)*root->len;
node *nxt=root->right;
if(!nxt){
root->len=limit*2;
root->slope=-c;
root->update();
return limit;
}
root->right=nullptr;
nxt->par=nullptr;
delete root;
root=left_most(nxt);
}
if(root->slope==-c){
T res=root->pos-root->len;
root->len=root->pos-(-limit);
root->update();
return res;
}
node *nd=new node();
nd->pos=root->pos-root->len;
nd->len=nd->pos-(-limit);
nd->slope=-c;
nd->par=root;
root->left=nd;
nd->update();
root->update();
return nd->pos;
}
T convolution_r(T c){
root=right_most(root);
if(root->slope<=c)return limit;
while(root->slope>c){
root->push();
node *nxt=root->left;
if(!nxt){
root->len=limit*2;
root->pos=limit;
root->slope=c;
root->update();
return -limit;
}
root->left=nullptr;
nxt->par=nullptr;
delete root;
root=right_most(nxt);
}
if(root->slope==c){
T res=root->pos;
root->len+=limit-root->pos;
root->pos=limit;
root->update();
return res;
}
node *nd=new node();
nd->pos=limit;
nd->len=limit-root->pos;
nd->slope=c;
nd->par=root;
root->right=nd;
nd->update();
root->update();
return root->pos;
}
std::pair<T,T>convolution_abs(T c){
T l=convolution_l(c);
T r=convolution_r(c);
return std::make_pair(l,r);
}
void convolution(SlopeTrick&rhs){
auto dfs=[&](auto self,node *nd)->void {
if(!nd)return;
nd->push();
node *rnd=nd->right;
self(self,nd->left);
search_slope(nd->slope);
if(nd->slope==root->slope){
node *l_tmp=root->left;
root->left=nullptr;
root->len+=nd->len;
root->propagate(0,nd->len);
root->push();
root->left=l_tmp;
root->update();
nd->left=nd->right=nullptr;
delete nd;
}
else if(nd->slope<root->slope){
node *l_tmp=root->left;
root->left=nullptr;
root->propagate(0,nd->len);
root->push();
root->left=nd;
nd->par=root;
nd->left=l_tmp;
nd->right=nullptr;
if(l_tmp)l_tmp->par=nd;
nd->pos=(l_tmp?l_tmp->posr:-limit)+nd->len;
nd->update();
root->update();
}
else{
node *r_tmp=root->right;
root->right=nd;
nd->par=root;
nd->left=nullptr;
nd->right=r_tmp;
if(r_tmp)r_tmp->par=nd;
if(nd->right)nd->right->propagate(0,nd->len);
nd->pos=(root->left?root->left->posr:-limit)+root->len+nd->len;
nd->update();
root->update();
}
self(self,rnd);
};
lv+=rhs.lv;
dfs(dfs,rhs.root);
rhs.root=nullptr;
auto [lnd,tmp]=split(root,0);
auto [mnd,rnd]=split(tmp,limit*2);
root=mnd;
root->propagate(0,-limit);
lv+=lnd->slope_sum;
delete lnd;
delete rnd;
}
T min(){
search_slope(0);
if(root->slope>=0){
if(!root->left)return lv;
return lv+root->left->slope_sum;
}
else{
T res=lv;
if(root->left)res+=root->left->slope_sum;
res+=root->slope*root->len;
return res;
}
}
std::pair<T,T>amin(){
search_slope(0);
if(root->slope==0){
T l=root->left?root->left->posr:-limit;
return std::make_pair(l,root->pos);
}
else if(root->slope>0){
T l=root->left?root->left->posr:-limit;
return std::make_pair(l,l);
}
else{
return std::make_pair(root->pos,root->pos);
}
}
T get(T x){
T res=lv;
T l=-limit;
while(true){
root->push();
T pl=l;
if(root->left)l=root->left->posr;
T r=root->pos;
if(l<=x&&x<=r){
if(root->left)res+=root->left->slope_sum;
res+=root->slope*(x-l);
break;
}
else if(x<l)root=root->left,l=pl;
else{
if(root->left)res+=root->left->slope_sum;
res+=root->slope*root->len;
l=root->pos;
root=root->right;
}
}
splay<node,true>(root);
return res;
}
void destruct(){
if(root)delete root;
root=nullptr;
}
std::vector<T>slice(T l,T r){
std::vector<T>res(r-l+1);
for(T i=l;i<=r;i++)res[i-l]=this->get(i);
return res;
}
};
constexpr ll inf=1e9+1000;
void SOLVE(){
int m,n;
cin>>m>>n;
vector<ll>a(m),b(n);
cin>>a>>b;
rep(k,1,m+1){
vector<pair<int,int>>c;
c.reserve(n+m);
rep(i,m)c.emplace_back(a[i],-1);
rep(i,n)c.emplace_back(b[i],k);
sort(all(c));
debug(c);
SlopeTrick<ll,1<<20>dp;
if(c[0].second==-1){
dp.add_abs(-1,inf);
}
else{
dp.add_r(c[0].second,inf);
dp.add_l(0,inf);
}
rep(i,1,c.size()){
if(c[i].first!=c[i-1].first){
dp.add_abs(0,c[i].first-c[i-1].first);
}
SlopeTrick<ll,1<<20>d;
if(c[i].second==-1){
d.add_abs(-1,inf);
}
else{
d.add_r(c[i].second,inf);
d.add_l(0,inf);
}
dp.convolution(d);
debug(dp.slice(-3,3));
}
cout<<dp.get(0)<<'\n';
dp.destruct();
}
}