Submission #423859

#	Time	Username	Problem	Language	Result	Execution time	Memory
423859		errorgorn	Treatment Project (JOI20_treatment)	C++17	100 / 100	919 ms	124328 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool used[100005];

struct node{
	int s,e,m;
	vector<ii> v;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void ins(int i,ii j){
		v.pub(j);
		
		if (s==e) return;
		if (i<=m) l->ins(i,j);
		else r->ins(i,j);
	}
	
	int query(int i,int j,int k){
		if (s==i && e==j){
			while (!v.empty() && used[v.back().se]) v.pob();
			if (v.empty()) return -1;
			
			if (v.back().fi<=k) return v.back().se;
			else return -1;
		}
		else if (j<=m) return l->query(i,j,k);
		else if (m<i) return r->query(i,j,k);
		else{
			int temp=l->query(i,m,k);
			if (temp==-1) return r->query(m+1,j,k);
			else return temp;
		}
	}
	
	void proc(){
		sort(all(v),[](ii i,ii j){
			return i>j;
		});
		
		if (s!=e) l->proc(),r->proc();
	}
} *root1=new node(0,100005),*root2=new node(0,100005);

int n,k;

struct E{
	int l,r;
	int t;
	ll cost;
	
	int dt; //discretized time
};
vector<E> v;

struct upd{
	int segno; //which tree
	int i,j,k;
	ll val;
};

struct cmp{
	bool operator () (upd i,upd j){
		return i.val>j.val;
	}
};

priority_queue<upd,vector<upd>,cmp> pq;

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	
	int a,b,c,d;
	rep(x,0,k){
		cin>>a>>b>>c>>d;
		v.pub({b,c+1,a,d});
	}
	
	vector<int> allt;
	rep(x,0,k) allt.pub(v[x].t);
	sort(all(allt));
	allt.erase(unique(all(allt)),allt.end());
	map<int,int> tid;
	rep(x,0,sz(allt)) tid[allt[x]]=x+1;
	rep(x,0,k) v[x].dt=tid[v[x].t];
	
	ll ans=1e18;
	
	rep(x,0,k){
		if (v[x].l==1){
			if (v[x].r==n+1) ans=min(ans,v[x].cost);
			
			pq.push(upd({1,v[x].dt,100005,v[x].r+v[x].t,v[x].cost}));
			pq.push(upd({2,0,v[x].dt-1,v[x].r-v[x].t,v[x].cost}));
		}
		else{
			root1->ins(v[x].dt,ii(v[x].l+v[x].t,x));
			root2->ins(v[x].dt,ii(v[x].l-v[x].t,x));
		}
	}
	
	root1->proc();
	root2->proc();
	
	while (!pq.empty()){
		upd u=pq.top();
		pq.pop();
		
		if (u.segno==1){
			while (true){
				int x=root1->query(u.i,u.j,u.k);
				if (x==-1) break;
				
				used[x]=true;
				
				pq.push(upd({1,v[x].dt,100005,v[x].r+v[x].t,v[x].cost+u.val}));
				pq.push(upd({2,0,v[x].dt-1,v[x].r-v[x].t,v[x].cost+u.val}));
				
				if (v[x].r==n+1) ans=min(ans,v[x].cost+u.val);
			}
		}
		else{
			while (true){
				int x=root2->query(u.i,u.j,u.k);
				if (x==-1) break;
				
				used[x]=true;
				
				pq.push(upd({1,v[x].dt,100005,v[x].r+v[x].t,v[x].cost+u.val}));
				pq.push(upd({2,0,v[x].dt-1,v[x].r-v[x].t,v[x].cost+u.val}));
				
				if (v[x].r==n+1) ans=min(ans,v[x].cost+u.val);
			}
		}
	}
	
	if (ans==1e18) cout<<"-1"<<endl;
	else cout<<ans<<endl;
}

Compilation message (stderr)

treatment.cpp: In constructor 'node::node(int, int)':
treatment.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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