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 optimize("unroll-loops")
using namespace std;
#define intt long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int M = (1<<19);
intt n , m , o;
vector<tuple<intt , intt , intt,intt>> intervals;
const intt INF = 1e18;
struct segTree
{
vector<intt> tree;
void init()
{
tree.assign(2*M , INF);
}
void upd(intt i , intt x)
{
tree[i + M] = min(tree[i + M] , x);
for(intt j = (i + M) / 2 ; j>=1;j/=2)
{
tree[j] = min(tree[2*j] , tree[2*j + 1]);
}
}
intt query(intt l , intt r)
{
l+=M;
r+=M;
if(l == r)
return tree[l];
intt lt = tree[l] , rt = tree[r];
while(l + 1 < r)
{
if(l % 2 == 0)
lt = min(lt , tree[l + 1]);
if(r%2 == 1)
rt = min(tree[r - 1] , rt);
l>>=1;
r>>=1;
}
return min(lt , rt);
}
}dp[2];
void rakkah()
{
map<intt ,intt> compress;
o = 1;
compress[n] = 1;
compress[o] = 1;
forr(i , 1 , m)
{
intt a , b , c , d;
cin>>a>>b>>c>>d;
compress[a] = compress[b] = compress[c] = 1;
intervals.pb({a , b , c , d});
}
intt cnt = 0;
for(auto p : compress)
{
compress[p.first] = cnt++;
}
n = compress[n] ;
o = compress[o];
for(auto &[a , b , c , d] : intervals)
{
a = compress[a] , b = compress[b] , c = compress[c];
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fore(i , 2)dp[i].init();
cin>>m>>n;
rakkah();
intt ans = INF;
fore(i , m)
{
auto [a , b , c ,d] = intervals[i];
intt cur[2] = {INF , INF};
if(a == o)
cur[0] = d;
if(b == n)
cur[1] = d;
fore(j , 2)
{
cur[j] = min(cur[j] , d + dp[j].query(a , b));
}
fore(j , 2)
dp[j].upd(c , cur[j]);
ans = min(ans , cur[0] + cur[1] - d);
}
cout<<(ans >= 1e17 ? -1 : ans)<<nl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |