oj.uz

Submission #331787

# Submission time Handle Problem Language Result Execution time Memory
331787 2020-11-30T06:29:07 Z YJU Treatment Project (JOI20_treatment) C++14
5 / 100
 825 ms 524292 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 825 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 2 ms 1388 KB Output is correct
9 Correct 2 ms 1152 KB Output is correct
10 Correct 3 ms 1260 KB Output is correct
11 Correct 2 ms 1388 KB Output is correct
12 Correct 3 ms 1516 KB Output is correct
13 Correct 2 ms 1516 KB Output is correct
14 Correct 3 ms 1516 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 2 ms 1388 KB Output is correct
9 Correct 2 ms 1152 KB Output is correct
10 Correct 3 ms 1260 KB Output is correct
11 Correct 2 ms 1388 KB Output is correct
12 Correct 3 ms 1516 KB Output is correct
13 Correct 2 ms 1516 KB Output is correct
14 Correct 3 ms 1516 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct
20 Correct 93 ms 27884 KB Output is correct
21 Correct 121 ms 27884 KB Output is correct
22 Correct 396 ms 236528 KB Output is correct
23 Correct 399 ms 236528 KB Output is correct
24 Incorrect 415 ms 260328 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 825 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -