Submission #1094609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094609		emptypringlescan	Treatment Project (JOI20_treatment)	C++17	100 / 100	449 ms	151748 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
pair<pair<int,int>,pair<int,int> > arr[100005];
pair<int,int> ran[100005];
struct node{
	int s,e,m;
	node *l, *r;
	int val;
	node(int S, int E){
		s=S; e=E;
		if(s+e>=0) m=(s+e)/2;
		else m=(s+e-1)/2;
		val=100004;
		l=r=NULL;
	}
	void prop(){
		if(l==NULL){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void update(int S, int V){
		if(s==e){
			val=V;
			return;
		}
		prop();
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		val=(ran[l->val].second<=ran[r->val].second?l->val:r->val);
	}
	int query(int S, int E){
		if(S<=s&&e<=E) return val;
		if(l==NULL) return 100004;
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else{
			int a=l->query(S,m),b=r->query(m+1,E);
			return (ran[a].second<=ran[b].second?a:b);
		}
	}
} *root;
bool cmp(int a, int b){
	return ran[a].second>ran[b].second;
}
unordered_map<int,vector<int> > um;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > pq;
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ran[100004]={2e9+5,2e9+5};
    int n,m;
    root=new node(-2e9-5,2e9+5);
    cin >> n >> m;
    for(int i=0; i<m; i++){
		int t,l,r,c;
		cin >> t >> l >> r >> c;
		arr[i]={{t,l},{r,c}};
		ran[i]={t-l,t+l};
		if(l==1){
			pq.push({c,i});
		}
		else um[t-l].push_back(i);
	}
	for(auto [i,j]:um){
		sort(um[i].begin(),um[i].end(),cmp);
		root->update(i,um[i].back());
		um[i].pop_back();
	}
	while(!pq.empty()){
		long long a=pq.top().first;
		int b=pq.top().second;
		pq.pop();
		if(arr[b].second.first==n){
			cout << a;
			return 0;
		}
		pair<int,int> qu={arr[b].first.first-arr[b].second.first-1,arr[b].first.first+arr[b].second.first+1};
		while(true){
			int x=root->query(qu.first,qu.second);
			if(x==100004||ran[x].second>qu.second) break;
			pq.push({a+arr[x].second.second,x});
			if(!um[ran[x].first].empty()){
				root->update(ran[x].first,um[ran[x].first].back());
				um[ran[x].first].pop_back();
			}
			else root->update(ran[x].first,100004);
		}
	}
	cout << -1;
	return 0;
}

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