Submission #527815

#	Time	Username	Problem	Language	Result	Execution time	Memory
527815		AriaH	Pinball (JOI14_pinball)	C++17	100 / 100	234 ms	27840 KiB

pinball

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 3e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

ll dis[2][N], seg[2][N << 2];

int LEN, n, L[N], R[N], C[N], cost[N];

vector < int > cm;

inline  int lwr(int x)
{
	return lower_bound(all(cm), x) - cm.begin();
}

void upd(int id, int p, ll x, int v = 1, int tl = 0, int tr = SZ(cm) - 1)
{
	if(tl == tr)
	{
		seg[id][v] = min(seg[id][v], x);
		return;
	}
	int mid = (tl + tr) >> 1;
	if(p <= mid) upd(id, p, x, v << 1, tl, mid);
	else upd(id, p, x, v << 1 | 1, mid + 1, tr);
	seg[id][v] = min(seg[id][v << 1], seg[id][v << 1 | 1]);
}

ll get(int id, int l, int r, int v = 1, int tl = 0, int tr = SZ(cm) - 1)
{
	if(l > tr || r < tl || l > r) return inf;
	if(l <= tl && tr <= r) return seg[id][v];
	int mid = (tl + tr) >> 1;
	return min(get(id, l, r, v << 1, tl, mid), get(id, l, r, v << 1 | 1, mid + 1, tr));
}

int main()
{
	fast_io;
	for(int j = 0; j < 2; j ++) for(int i = 0; i < N << 2; i ++) seg[j][i] = inf;
	cin >> n >> LEN;
	cm.push_back(0);
	cm.push_back(LEN);
	for(int i = 0; i <= n + 1; i ++) dis[0][i] = dis[1][i] = inf;
	for(int i = 1; i <= n; i ++)
	{
		cin >> L[i] >> R[i] >> C[i] >> cost[i];
		cm.push_back(L[i]);
		cm.push_back(R[i]);
		cm.push_back(C[i]);
		if(L[i] == 1)
		{
			dis[0][i] = 0;
		}
		if(R[i] == LEN)
		{
			dis[1][i] = 0;
		}
	}
	sort(all(cm));
	cm.resize(unique(all(cm)) - cm.begin());
	ll tot = inf;
	for(int i = 1; i <= n; i ++)
	{
		L[i] = lwr(L[i]);
		R[i] = lwr(R[i]);
		C[i] = lwr(C[i]);
		///printf("i = %d L = %d R = %d C = %d\n", i, L[i], R[i], C[i]);
		dis[0][i] = min(dis[0][i], get(0, L[i], R[i])) + cost[i];
		dis[1][i] = min(dis[1][i], get(1, L[i], R[i])) + cost[i];
		///printf("i = %d dis0 = %lld dis1 = %lld cost = %d\n", i, dis[0][i], dis[1][i], cost[i]);
		tot = min(tot, dis[0][i] + dis[1][i] - cost[i]);
		upd(0, C[i], dis[0][i]);
		upd(1, C[i], dis[1][i]);
	}
	if(tot >= inf / 2) tot = -1;
	cout << tot;
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49