Submission #423833

#	Time	Username	Problem	Language	Result	Execution time	Memory
423833		errorgorn	Treatment Project (JOI20_treatment)	C++17	4 / 100	1437 ms	275704 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());

struct node{
	int s,e,m;
	set<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.insert(j);
		
		if (s==e) return;
		if (i<=m) l->ins(i,j);
		else r->ins(i,j);
	}
	
	void rem(int i,ii j){
		v.erase(j);
		
		if (s==e) return;
		if (i<=m) l->rem(i,j);
		else r->rem(i,j);
	}
	
	int query(int i,int j,int k){
		if (s==i && e==j){
			if (v.empty()) return -1;
			
			if ((*v.begin()).fi<=k) return (*v.begin()).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;
		}
	}
} *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});
	}
	
	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].t,100005,v[x].r+v[x].t,v[x].cost}));
			pq.push(upd({2,0,v[x].t-1,v[x].r-v[x].t,v[x].cost}));
		}
		else{
			root1->ins(v[x].t,ii(v[x].l+v[x].t,x));
			root2->ins(v[x].t,ii(v[x].l-v[x].t,x));
		}
	}
	
	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;
				
				pq.push(upd({1,v[x].t,100005,v[x].r+v[x].t,v[x].cost+u.val}));
				pq.push(upd({2,0,v[x].t-1,v[x].r-v[x].t,v[x].cost+u.val}));
				
				root1->rem(v[x].t,ii(v[x].l+v[x].t,x));
				root2->rem(v[x].t,ii(v[x].l-v[x].t,x));
				
				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;
				
				pq.push(upd({1,v[x].t,100005,v[x].r+v[x].t,v[x].cost+u.val}));
				pq.push(upd({2,0,v[x].t-1,v[x].r-v[x].t,v[x].cost+u.val}));
				
				root1->rem(v[x].t,ii(v[x].l+v[x].t,x));
				root2->rem(v[x].t,ii(v[x].l-v[x].t,x));
				
				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:27:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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