Submission #50273

#	Time	Username	Problem	Language	Result	Execution time	Memory
50273		MatheusLealV	Pinball (JOI14_pinball)	C++17	100 / 100	952 ms	97176 KiB

pinball

#include <bits/stdc++.h>
#define N 100050
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
typedef long long ll;
#define inf 1000000000000000000LL
using namespace std;

struct segtree
{
	ll tree[11*N];

	inline void init()
	{
		for(int i = 0; i < 11*N; i++) tree[i] = inf;
	}

	inline void upd(int nod, int a, int b, int i, int j, ll x)
	{
		if(a == b)
		{
			tree[nod] = min(tree[nod], x);

			return;
		}

		if(i <= mid) upd(l, a, mid, i, j, x);

		else upd(r, mid + 1, b, i, j, x);

		tree[nod] = min(tree[l], tree[r]);
	}

	inline ll query(int nod, int a, int b, int i, int j)
	{
		if(i <= a && j >= b) return tree[nod];

		ll best = inf;

		if( !(j < a || i > mid) ) best = min(best, query(l, a, mid, i, j));

		if( !(j < mid + 1 || i > b)) best = min(best, query(r, mid + 1, b, i, j));

		return best;
	}

} tree[2][2];

int n, m, A[N], B[N], C[N], zero[N];

ll ans = inf, dp[N][2][2], D[N];

int bit[3*N];

inline void upd(int x, int v)
{
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}

inline int query(int x)
{
	int sum = 0; 

	for(int i = x; i > 0; i -= (i&-i)) sum += bit[i];

	return sum;
}

vector<int> val;

map<int, int> mapa;

int rev[3*N], cnt, M = 0;

inline void compress()
{
	sort(val.begin(), val.end());

	for(auto x: val)
	{
		if(!mapa[x])
		{
			mapa[x] = ++cnt;

			rev[cnt] = x;
		}
	}

	for(int i = 1; i <= n; i++)
	{
		A[i] = mapa[A[i]];

		B[i] = mapa[B[i]];

		C[i] = mapa[C[i]];

		M = max(M, max(A[i], max(B[i], C[i])));
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1; i <= n; i++)
	{
		cin>>A[i]>>B[i]>>C[i]>>D[i];

		val.push_back(A[i]);

		val.push_back(B[i]);

		val.push_back(C[i]);
	}

	compress();

	for(int i = 1; i <= n; i++)
	{
		if(query(B[i]) - query(A[i] - 1) != B[i] - A[i] + 1) zero[i] = 1;

		upd(A[i], 1), upd(B[i] + 1, -1);
	}

	for(int j = 0; j < 2; j++)
	{
		for(int z = 0; z < 2; z++)
		{
			for(int i = 1; i <= n; i++) dp[i][j][z] = inf;

			tree[j][z].init();
		}
	}

	for(int i = 1; i <= n; i++)
	{
		int tl = (rev[A[i]] == 1), tr = (rev[B[i]] == m);

		int ok[2][2] = {0};

		for(int j = 0; j < 2; j++)
		{
			for(int z = 0; z < 2; z++)
			{
				int L = (j || tl), R = (z || tr);

				if(ok[L][R]) continue;

				ok[L][R] = 1;

				dp[i][L][R] = min(dp[i][L][R], tree[j][z].query(1, 1, M, A[i], B[i]) + D[i]);
			}
		}

		for(int j = 0; j < 2; j++)
			for(int z = 0; z < 2; z++)
				tree[j][z].upd(1, 1, M, C[i], C[i], dp[i][j][z]);

		if(zero[i])
		{
			dp[i][tl][tr] = D[i];

			tree[tl][tr].upd(1, 1, M, C[i], C[i], D[i]);	
		}

		ans = min(ans, min(dp[i][1][1], dp[i][0][1] + dp[i][1][0] - D[i]));
	}

	cout<<(ans == inf ? -1 : ans)<<"\n";
}

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