This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
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 (stderr)
pinball.cpp: In function 'int main()':
pinball.cpp:116:45: error: no matching function for call to 'min(ll)'
res.fill = min(res.fill+pay[i]+que.L+que.R);
^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from pinball.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
min(const _Tp& __a, const _Tp& __b)
^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: template argument deduction/substitution failed:
pinball.cpp:116:45: note: candidate expects 2 arguments, 1 provided
res.fill = min(res.fill+pay[i]+que.L+que.R);
^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from pinball.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: template argument deduction/substitution failed:
pinball.cpp:116:45: note: candidate expects 3 arguments, 1 provided
res.fill = min(res.fill+pay[i]+que.L+que.R);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from pinball.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
min(initializer_list<_Tp> __l)
^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
pinball.cpp:116:45: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
res.fill = min(res.fill+pay[i]+que.L+que.R);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from pinball.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
min(initializer_list<_Tp> __l, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
pinball.cpp:116:45: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
res.fill = min(res.fill+pay[i]+que.L+que.R);
^
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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~