#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=250005, inf=1e9;
ll n, k, res=1e18;
pair<ll, ll> p[nx];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
struct persist
{
struct node
{
ll mn;
node *l, *r;
node(ll mn=1e18): mn(mn), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx];
void update(int l, int r, pnode &k, pnode t, int idx, ll vl)
{
//printf("update %d %d\n", l, r);
if (t) k=new node(*t);
else k=new node();
if (l==r) return k->mn=vl, void();
ll md=l+(r-l)/2;
if (idx<=md) update(l, md, k->l, t?t->l:0, idx, vl);
else update(md+1, r, k->r, t?t->r:0, idx, vl);
k->mn=min((k->l)?k->l->mn:1e18, (k->r)?k->r->mn:1e18);
}
ll query(int l, int r, pnode k, int ql, int qr)
{
if (r<ql||qr<l|!k) return 1e18;
if (ql<=l&&r<=qr) return k->mn;
ll md=l+(r-l)/2;
return min(query(l, md, k->l, ql, qr), query(md+1, r, k->r, ql, qr));
}
} up, dn;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>p[i].first>>p[i].second;
sort(p+1, p+n+1);
for (int i=1; i<=n; i++)
{
//printf("here %d\n", i);
res=min(res, up.query(-inf, inf, up.rt[i], p[i].second, inf)+p[i].first-p[i].second);
res=min(res, dn.query(-inf, inf, dn.rt[i], -inf, p[i].second)+p[i].first+p[i].second);
//printf("here %d\n", i);
up.update(-inf, inf, up.rt[i+1], up.rt[i], p[i].second, -p[i].first+p[i].second);
dn.update(-inf, inf, dn.rt[i+1], dn.rt[i], p[i].second, -p[i].first-p[i].second);
}
cout<<res;
}
Compilation message
road_construction.cpp: In member function 'long long int persist::query(int, int, persist::pnode, int, int)':
road_construction.cpp:36:21: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
36 | if (r<ql||qr<l|!k) return 1e18;
| ~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
507 ms |
496720 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
804 ms |
513084 KB |
Output is correct |
2 |
Correct |
779 ms |
513104 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
521 ms |
496320 KB |
Output is correct |
5 |
Correct |
630 ms |
513104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
804 ms |
513084 KB |
Output is correct |
2 |
Correct |
779 ms |
513104 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
521 ms |
496320 KB |
Output is correct |
5 |
Correct |
630 ms |
513104 KB |
Output is correct |
6 |
Incorrect |
771 ms |
513088 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |