oj.uz

Submission #36014

# Submission time Handle Problem Language Result Execution time Memory
36014 2017-12-04T08:26:05 Z YoLo Pinball (JOI14_pinball) C++14
100 / 100
 409 ms 14680 KB 
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
#define N 1000000
#define lmax LONG_LONG_MAX
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
int n, m, lef[100009], rig[100009], a[100009], b[100009], c[100009], d[100009], f[100009], itl[400009], itr[400009], p[100009], ans = lmax;
void updl(int k, int l, int r, int pos, int val)
{
	if(r < pos || l > pos || r < l)
		return;
	if(r == pos && l == pos)
	{
		itl[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	updl(k * 2, l, mid, pos, val);
	updl(k * 2 + 1, mid + 1, r, pos, val);
	itl[k] = min(itl[k * 2], itl[k * 2 + 1]);
}
int getl(int k, int l, int r, int L, int R)
{
	if(r < L || R < l || r < l)
		return 1e18;
	if(L <= l && r <= R)
		return itl[k];
	int mid = (l + r) / 2;
	return min(getl(k * 2, l, mid, L, R), getl(k * 2 + 1, mid + 1, r, L, R));
}
void updr(int k, int l, int r, int pos, int val)
{
	if(r < pos || l > pos || r < l)
		return;
	if(r == pos && l == pos)
	{
		itr[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	updr(k * 2, l, mid, pos, val);
	updr(k * 2 + 1, mid + 1, r, pos, val);
	itr[k] = min(itr[k * 2], itr[k * 2 + 1]);
}
int getr(int k, int l, int r, int L, int R)
{
	if(r < L || R < l || r < l)
		return 1e18;
	if(L <= l && r <= R)
		return itr[k];
	int mid = (l + r) / 2;
	return min(getr(k * 2, l, mid, L, R), getr(k * 2 + 1, mid + 1, r, L, R));
}
bool cmp(int u, int v)
{
	return c[u] < c[v];
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		cin >> a[i] >> b[i] >> c[i] >> d[i], f[i] = i;
	sort(f + 1, f + 1 + n, cmp);
	for(int i = 1; i <= n; i ++)
		p[f[i]] = i;
	for(int i = 1; i <= 400000; i ++)
		itl[i] = itr[i] = 1e18;
	for(int i = 1; i <= n; i ++)
	{
		int l = 1;
		int r = n;
		while(l < r)
		{
			int mid = (l + r) / 2;
			if(c[f[mid]] < a[i])
				l = mid + 1;
			else
				r = mid;
		}
		int ll = l;
		l = 1;
		r = n;
		while(l < r)
		{
			int mid = (l + r + 1) / 2;
			if(c[f[mid]] > b[i])
				r = mid - 1;
			else
				l = mid;
		}
		int rr = l;
		if(a[i] == 1)
			lef[i] = d[i];
		else
		{
			int tak = getl(1, 1, n, ll, rr);
			if(tak < 1e18)
				lef[i] = tak + d[i];
		}
		if(lef[i] > 0)
			updl(1, 1, n, p[i], lef[i]);
		if(b[i] == m)
			rig[i] = d[i];
		else
		{
			int tak = getr(1, 1, n, ll, rr);
			if(tak < 1e18)
				rig[i] = tak + d[i];
		}
		if(rig[i] > 0)
			updr(1, 1, n, p[i], rig[i]);
		if(rig[i] > 0 && lef[i] > 0)
			ans = min(ans, rig[i] + lef[i] - d[i]);
		//cout << i << ' ' << l << ' ' << r << ' ' << p[i] << ' ' << lef[i] << ' ' << rig[i] << endl;
	}
	if(ans < 1e16)
		cout << ans;
	else
		cout << -1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 0 ms 14680 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 0 ms 14680 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 0 ms 14680 KB Output is correct
8 Correct 0 ms 14680 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 0 ms 14680 KB Output is correct
3 Correct 0 ms 14680 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 0 ms 14680 KB Output is correct
6 Correct 0 ms 14680 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 6 ms 14680 KB Output is correct
5 Correct 0 ms 14680 KB Output is correct
6 Correct 0 ms 14680 KB Output is correct
7 Correct 0 ms 14680 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 0 ms 14680 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14680 KB Output is correct
2 Correct 73 ms 14680 KB Output is correct
3 Correct 269 ms 14680 KB Output is correct
4 Correct 383 ms 14680 KB Output is correct
5 Correct 159 ms 14680 KB Output is correct
6 Correct 409 ms 14680 KB Output is correct
7 Correct 373 ms 14680 KB Output is correct
8 Correct 396 ms 14680 KB Output is correct
9 Correct 36 ms 14680 KB Output is correct
10 Correct 156 ms 14680 KB Output is correct
11 Correct 193 ms 14680 KB Output is correct
12 Correct 303 ms 14680 KB Output is correct
13 Correct 256 ms 14680 KB Output is correct
14 Correct 256 ms 14680 KB Output is correct