oj.uz

Submission #50273

# Submission time Handle Problem Language Result Execution time Memory
50273 2018-06-09T01:45:43 Z MatheusLealV Pinball (JOI14_pinball) C++17
100 / 100
 952 ms 97176 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 34936 KB Output is correct
2 Correct 31 ms 35048 KB Output is correct
3 Correct 29 ms 35096 KB Output is correct
4 Correct 26 ms 35096 KB Output is correct
5 Correct 27 ms 35136 KB Output is correct
6 Correct 28 ms 35136 KB Output is correct
7 Correct 26 ms 35136 KB Output is correct
8 Correct 29 ms 35136 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 35208 KB Output is correct
2 Correct 29 ms 35344 KB Output is correct
3 Correct 27 ms 35344 KB Output is correct
4 Correct 30 ms 35344 KB Output is correct
5 Correct 27 ms 35372 KB Output is correct
6 Correct 29 ms 35524 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35524 KB Output is correct
2 Correct 28 ms 35524 KB Output is correct
3 Correct 29 ms 35548 KB Output is correct
4 Correct 28 ms 35584 KB Output is correct
5 Correct 32 ms 35644 KB Output is correct
6 Correct 31 ms 35644 KB Output is correct
7 Correct 28 ms 35644 KB Output is correct
8 Correct 30 ms 35760 KB Output is correct
9 Correct 32 ms 35800 KB Output is correct
10 Correct 31 ms 35844 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 37548 KB Output is correct
2 Correct 192 ms 41588 KB Output is correct
3 Correct 511 ms 49540 KB Output is correct
4 Correct 292 ms 49868 KB Output is correct
5 Correct 362 ms 53472 KB Output is correct
6 Correct 397 ms 56612 KB Output is correct
7 Correct 810 ms 68384 KB Output is correct
8 Correct 670 ms 69824 KB Output is correct
9 Correct 121 ms 69824 KB Output is correct
10 Correct 410 ms 70848 KB Output is correct
11 Correct 562 ms 85520 KB Output is correct
12 Correct 952 ms 89408 KB Output is correct
13 Correct 832 ms 93284 KB Output is correct
14 Correct 721 ms 97176 KB Output is correct