Submission #331787

#	Time	Username	Problem	Language	Result	Execution time	Memory
331787		YJU	Treatment Project (JOI20_treatment)	C++14	5 / 100	825 ms	524292 KiB

treatment

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<40);
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()


struct SRC{
	ll T,L,R,C;
}plan;

ll ans=INF,n,m;
vector<SRC> L,M,R;

struct seg{
	ll ly,ry,val;
	seg *ls,*rs;
	void ins(ll to,ll d){
		if(ly==ry-1){val=min(val,d);return;}
		ll mid=(ly+ry)/2;
		if(to<mid){
			if(!ls)ls=new seg{ly,mid,INF,0,0};
			ls->ins(to,d);
		}else{
			if(!rs)rs=new seg{mid,ry,INF,0,0};
			rs->ins(to,d);
		}
		val=min((rs?rs->val:INF),(ls?ls->val:INF));
		return;
	}
	ll Q(ll qly,ll qry){
		if(ly>=qly&&ry<=qry)return val;
		if(ly>=qry||ry<=qly)return INF;
		ll mid=(ry+ly)/2;
		return min((ls?ls->Q(qly,qry):INF),(rs?rs->Q(qly,qry):INF));
	}
};

struct node{
	ll lx,rx;
	seg *S;
	node *lc,*rc;
	void add(ll tox,ll toy,ll d){
		S->ins(toy,d);
		if(lx==rx-1){return ;}
		ll mid=(lx+rx)/2;
		if(tox<mid){
			if(!lc)lc=new node{lx,mid,new seg{-N,N,INF,0,0},0,0};
			lc->add(tox,toy,d);
		}else{
			if(!rc)rc=new node{mid,rx,new seg{-N,N,INF,0,0},0,0};
			rc->add(tox,toy,d);
		}
	}
	ll Q(ll qlx,ll qrx,ll qly,ll qry){
		if(lx>=qlx&&rx<=qrx)return S->Q(qly,qry);
		if(lx>=qrx||rx<=qlx)return INF;
		ll mid=(qlx+qrx)/2;
		return min((lc?lc->Q(qlx,qrx,qly,qry):INF),(rc?rc->Q(qlx,qrx,qly,qry):INF));
	}
}*rt=new node{-N,N,new seg{-N,N,INF,0,0},0,0};

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP(i,m){
		cin>>plan.T>>plan.L>>plan.R>>plan.C;
		if(plan.L==1&&plan.R==n){
			ans=min(ans,plan.C);
		}else if(plan.L==1){
			L.pb(plan);
		}else if(plan.R==n){
			R.pb(plan);
		}else{
			M.pb(plan);
		}
	}
	for(auto i:R){
		rt->add(i.L+i.T-1,i.L-i.T-1,i.C);
		//add(ra,i.L+i.T-1,i.C);
		//add(rb,i.L-i.T-1,i.C);
	}
	sort(M.begin(),M.end(),[](SRC A,SRC B){
		return A.L>B.L;
	});
	for(auto i:M){
		//ll res=min(q(ra,-INF,i.R+i.T+1),q(rb,-INF,i.R-i.T+1));
		ll res=rt->Q(-INF,i.R+i.T+1,-INF,i.R-i.T+1);
		rt->add(i.L+i.T-1,i.L-i.T-1,i.C+res);
		//add(ra,i.L+i.T-1,i.C+res);
		//add(rb,i.L-i.T-1,i.C+res);
	}
	for(auto i:L){
		ans=min(ans,i.C+rt->Q(-INF,i.R+i.T+1,-INF,i.R-i.T+1));
	}
	if(ans>=INF)ans=-1;
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

treatment.cpp: In member function 'll seg::Q(ll, ll)':
treatment.cpp:51:6: warning: unused variable 'mid' [-Wunused-variable]
   51 |   ll mid=(ry+ly)/2;
      |      ^~~
treatment.cpp: In member function 'll node::Q(ll, ll, ll, ll)':
treatment.cpp:75:6: warning: unused variable 'mid' [-Wunused-variable]
   75 |   ll mid=(qlx+qrx)/2;
      |      ^~~

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61