Submission #894271

#	Time	Username	Problem	Language	Result	Execution time	Memory
894271		denniskim	Treatment Project (JOI20_treatment)	C++17	100 / 100	385 ms	60596 KiB

treatment

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll T, L, R, C;
};

struct gujo2
{
	ll A, B, C, D, num;
};

ll n, m;
gujo b[500010];
gujo2 a[500010];
vector<pll> vec[500010];
ll dist[500010];
vector<ll> zip;
priority_queue<pll> pq;
ll P[500010];
ll ans = INF;

struct segtree
{
	pll seg[2000010];
	
	void update(ll no, ll s, ll e, ll w, ll v1, ll v2)
	{
		if(e < w || w < s)
			return;
		
		if(s == e)
		{
			seg[no] = {v1, v2};
			return;
		}
		
		update(no << 1, s, (s + e) >> 1, w, v1, v2);
		update(no << 1 | 1, ((s + e) >> 1) + 1, e, w, v1, v2);
		
		seg[no] = min(seg[no << 1], seg[no << 1 | 1]);
	}
	
	pll query(ll no, ll s, ll e, ll l, ll r)
	{
		if(e < l || r < s)
			return {INF, -1};
		
		if(l <= s && e <= r)
			return seg[no];
		
		pll L = query(no << 1, s, (s + e) >> 1, l, r);
		pll R = query(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r);
		
		return min(L, R);
	}
}segt;

int main(void)
{
	//fastio
	
	cin >> n >> m;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		cin >> b[i].T >> b[i].L >> b[i].R >> b[i].C;
		
		a[i].A = b[i].L + b[i].T;
		a[i].B = b[i].R + b[i].T + 1;
		a[i].C = b[i].L - b[i].T;
		a[i].D = b[i].R - b[i].T + 1;
		a[i].num = i;
		zip.push_back(a[i].A), zip.push_back(a[i].B), zip.push_back(a[i].C), zip.push_back(a[i].D);
	}
	
	compress(zip);
	
	for(ll i = 1 ; i <= m ; i++)
	{
		a[i].A = lower_bound(zip.begin(), zip.end(), a[i].A) - zip.begin() + 1;
		a[i].B = lower_bound(zip.begin(), zip.end(), a[i].B) - zip.begin() + 1;
		a[i].C = lower_bound(zip.begin(), zip.end(), a[i].C) - zip.begin() + 1;
		a[i].D = lower_bound(zip.begin(), zip.end(), a[i].D) - zip.begin() + 1;
	}
	
	for(ll i = 1 ; i <= m ; i++)
		dist[i] = INF;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(b[i].L == 1)
		{
			dist[i] = b[i].C;
			pq.push({-b[i].C, i});
		}
		
		vec[a[i].C].push_back({a[i].A, a[i].num});
	}
	
	ll siz = (ll)zip.size();
	
	for(ll i = 1 ; i <= siz ; i++)
	{
		sort(vec[i].begin(), vec[i].end());
		
		if(!vec[i].empty())
		{
			P[i] = 1;
			segt.update(1, 1, siz, i, vec[i][0].fi, vec[i][0].se);
		}
		
		else
			segt.update(1, 1, siz, i, INF, -1);
	}
	
	while(!pq.empty())
	{
		pll qq = pq.top();
		pq.pop();
		
		while(1)
		{
			pll gap = segt.query(1, 1, siz, 1, a[qq.se].D);
			
			if(gap.fi > a[qq.se].B)
				break;
			
			if(dist[gap.se] == INF)
			{
				dist[gap.se] = dist[qq.se] + b[gap.se].C;
				pq.push({-dist[gap.se], gap.se});
			}
			
			if(P[a[gap.se].C] >= (ll)vec[a[gap.se].C].size())
				segt.update(1, 1, siz, a[gap.se].C, INF, -1);
			
			else
			{
				segt.update(1, 1, siz, a[gap.se].C, vec[a[gap.se].C][P[a[gap.se].C]].fi, vec[a[gap.se].C][P[a[gap.se].C]].se);
				P[a[gap.se].C]++;
			}
		}
	}
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(b[i].R == n)
			ans = min(ans, dist[i]);
	}
	
	if(ans == INF)
		cout << -1;
	else
		cout << ans;
	
	return 0;
}

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