oj.uz

Submission #990981

# Submission time Handle Problem Language Result Execution time Memory
990981 2024-06-01T03:05:41 Z 12345678 Road Construction (JOI21_road_construction) C++17
7 / 100
 804 ms 513104 KB 
#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;
      |                   ~~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 496720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 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

Subtask #4
0 / 20.0

# 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 -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -