oj.uz

Submission #148089

# Submission time Handle Problem Language Result Execution time Memory
148089 2019-08-31T13:45:35 Z WhipppedCream Pinball (JOI14_pinball) C++17
100 / 100
 597 ms 77540 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;
int n, m;

int A[maxn], B[maxn], C[maxn], pay[maxn];
vector<int> cut;
map<int, int> bst;

struct node
{
	ll L, R, fill;
	node() : L(1e18), R(1e18), fill(1e18){}
	node(ll L, ll R, ll fill) : L(L), R(R), fill(fill){}
};

node st[24*maxn];
int cnt;

node pull(node x, node y)
{
	node a;
	a.L = min(x.L, y.L);
	a.R = min(x.R, y.R);
	a.fill = min(x.fill, y.fill);
	return a;
}

void build(int p = 1, int L = 1, int R = cnt)
{
	if(L == R) 
	{
		st[p] = node();
		return;
	}
	int M = (L+R)/2;
	build(2*p, L, M);
	build(2*p+1, M+1, R);
	st[p] = pull(st[2*p], st[2*p+1]);
}

node ask(int i, int j, int p = 1, int L = 1, int R = cnt)
{
	if(i> R || j< L) return node();
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	node x = ask(i, j, 2*p, L, M);
	node y = ask(i, j, 2*p+1, M+1, R);
	node res = pull(x, y);
	return res;
}

void update(int x, node dx, int p = 1, int L = 1, int R = cnt)
{
	if(L == R)
	{
		node res = pull(dx, st[p]);
		st[p] = res;
		return;
	}
	int M = (L+R)/2;
	if(x<= M) update(x, dx, 2*p, L, M);
	else update(x, dx, 2*p+1, M+1, R);
	st[p] = pull(st[2*p], st[2*p+1]);
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i<= n; i++)
	{
		scanf("%d %d %d %d", &A[i], &B[i], &C[i], &pay[i]);
		cut.pb(A[i]); cut.pb(B[i]); cut.pb(C[i]);
	}
	sort(cut.begin(), cut.end());
	cut.resize(unique(cut.begin(), cut.end())-cut.begin());
	if(cut[0] != 1) cnt++;
	for(int i = 0; i+1< (int) cut.size(); i++)
	{
		int x = cut[i];
		cnt++;
		bst[x] = cnt;
		if(x+1 != cut[i+1]) cnt++;
	}
	cnt++;
	bst[cut.back()] = cnt;
	if(cut.back() != m) cnt++;
	for(int i = 1; i<= n; i++)
	{
		A[i] = bst[A[i]];
		B[i] = bst[B[i]];
		C[i] = bst[C[i]];
	}
	build();
	ll best = 1e18;
	for(int i = 1; i<= n; i++)
	{
		node que = ask(A[i], B[i]);
		node res;
		res.L = que.L+pay[i];
		if(A[i] == 1) res.L = min(res.L, 1LL*pay[i]);
		res.R = que.R+pay[i];
		if(B[i] == cnt) res.R = min(res.R, 1LL*pay[i]);
		res.fill = que.fill+pay[i];
		if(A[i] == 1 && B[i] == cnt) res.fill = min(res.fill, 1LL*pay[i]);
		if(A[i] == 1) res.fill = min(res.fill, pay[i]+que.R);
		if(B[i] == cnt) res.fill = min(res.fill, pay[i]+que.L);
		res.fill = min(res.fill, pay[i]+que.L+que.R);
		update(C[i], res);
		// printf("{%lld %lld %lld}\n", res.L, res.R, res.fill);
		best = min(best, res.fill);
	}
	if(best == 1e18) printf("-1\n");
	else printf("%lld\n", best);
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &A[i], &B[i], &C[i], &pay[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56696 KB Output is correct
2 Correct 57 ms 56668 KB Output is correct
3 Correct 75 ms 56672 KB Output is correct
4 Correct 51 ms 56696 KB Output is correct
5 Correct 51 ms 56696 KB Output is correct
6 Correct 54 ms 56696 KB Output is correct
7 Correct 51 ms 56696 KB Output is correct
8 Correct 51 ms 56668 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56696 KB Output is correct
2 Correct 57 ms 56668 KB Output is correct
3 Correct 75 ms 56672 KB Output is correct
4 Correct 51 ms 56696 KB Output is correct
5 Correct 51 ms 56696 KB Output is correct
6 Correct 54 ms 56696 KB Output is correct
7 Correct 51 ms 56696 KB Output is correct
8 Correct 51 ms 56668 KB Output is correct
9 Correct 52 ms 56668 KB Output is correct
10 Correct 51 ms 56696 KB Output is correct
11 Correct 51 ms 56732 KB Output is correct
12 Correct 52 ms 56788 KB Output is correct
13 Correct 51 ms 56740 KB Output is correct
14 Correct 51 ms 56796 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56696 KB Output is correct
2 Correct 57 ms 56668 KB Output is correct
3 Correct 75 ms 56672 KB Output is correct
4 Correct 51 ms 56696 KB Output is correct
5 Correct 51 ms 56696 KB Output is correct
6 Correct 54 ms 56696 KB Output is correct
7 Correct 51 ms 56696 KB Output is correct
8 Correct 51 ms 56668 KB Output is correct
9 Correct 52 ms 56668 KB Output is correct
10 Correct 51 ms 56696 KB Output is correct
11 Correct 51 ms 56732 KB Output is correct
12 Correct 52 ms 56788 KB Output is correct
13 Correct 51 ms 56740 KB Output is correct
14 Correct 51 ms 56796 KB Output is correct
15 Correct 51 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct
17 Correct 53 ms 56824 KB Output is correct
18 Correct 52 ms 56800 KB Output is correct
19 Correct 54 ms 56824 KB Output is correct
20 Correct 53 ms 56824 KB Output is correct
21 Correct 52 ms 56824 KB Output is correct
22 Correct 53 ms 56928 KB Output is correct
23 Correct 53 ms 56920 KB Output is correct
24 Correct 53 ms 56952 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56696 KB Output is correct
2 Correct 57 ms 56668 KB Output is correct
3 Correct 75 ms 56672 KB Output is correct
4 Correct 51 ms 56696 KB Output is correct
5 Correct 51 ms 56696 KB Output is correct
6 Correct 54 ms 56696 KB Output is correct
7 Correct 51 ms 56696 KB Output is correct
8 Correct 51 ms 56668 KB Output is correct
9 Correct 52 ms 56668 KB Output is correct
10 Correct 51 ms 56696 KB Output is correct
11 Correct 51 ms 56732 KB Output is correct
12 Correct 52 ms 56788 KB Output is correct
13 Correct 51 ms 56740 KB Output is correct
14 Correct 51 ms 56796 KB Output is correct
15 Correct 51 ms 56696 KB Output is correct
16 Correct 51 ms 56696 KB Output is correct
17 Correct 53 ms 56824 KB Output is correct
18 Correct 52 ms 56800 KB Output is correct
19 Correct 54 ms 56824 KB Output is correct
20 Correct 53 ms 56824 KB Output is correct
21 Correct 52 ms 56824 KB Output is correct
22 Correct 53 ms 56928 KB Output is correct
23 Correct 53 ms 56920 KB Output is correct
24 Correct 53 ms 56952 KB Output is correct
25 Correct 75 ms 58104 KB Output is correct
26 Correct 143 ms 60912 KB Output is correct
27 Correct 342 ms 66028 KB Output is correct
28 Correct 223 ms 63692 KB Output is correct
29 Correct 258 ms 64364 KB Output is correct
30 Correct 286 ms 64140 KB Output is correct
31 Correct 491 ms 71144 KB Output is correct
32 Correct 442 ms 68964 KB Output is correct
33 Correct 108 ms 60792 KB Output is correct
34 Correct 273 ms 67108 KB Output is correct
35 Correct 388 ms 77416 KB Output is correct
36 Correct 597 ms 77540 KB Output is correct
37 Correct 513 ms 77540 KB Output is correct
38 Correct 506 ms 77472 KB Output is correct