#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[12*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);
}
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] == m) res.R = min(res.R, 1LL*pay[i]);
res.fill = que.fill+pay[i];
res.fill = min(res.fill, que.L+que.R+pay[i]);
if(A[i] == 1 && B[i] == m) res.fill = min(res.fill, 1LL*pay[i]);
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:76: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:79: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
