Submission #476881

#	Time	Username	Problem	Language	Result	Execution time	Memory
476881		nafis_shifat	Road Construction (JOI21_road_construction)	C++17	13 / 100	1494 ms	742732 KiB

road_construction

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,int>
#define f first
#define s second
using namespace std;
const int mxn = 2e6+5;
const ll inf = 1e15;
pii PP = {inf, -1};
struct node
{
    node *left,*right;
    pii val;
    node(pii _v = PP, node *l = NULL, node *r = NULL) : val(_v), left(l), right(r){};
    node *update(int l,int r,int p,ll v) {
        if(l > p || r < p) return this;
        if(l == r) {
            return new node({v, l});
        }


        int mid = l + r >> 1;
        node *ret = new node();
        if(left == NULL) left = new node();
        if(right == NULL) right = new node();
        ret-> left = left-> update(l, mid, p, v);
        ret-> right = right-> update(mid + 1, r, p, v);
        ret-> val = min(ret-> left -> val, ret-> right -> val);
        return ret;
    }

    pii query(int l,int r, int s, int t) {
        if(l > t || r < s) return {inf,-1};
        if(l >= s && r <= t) return val;

        int mid = l + r >> 1;

        if(left == NULL) left = new node();
        if(right == NULL) right = new node();

        return min(left-> query(l, mid, s, t), right-> query(mid + 1, r, s, t));
    }
}*root1[mxn], *root2[mxn];


int pos[mxn], inv[mxn];

int id1[mxn], id2[mxn];
int n,k;
vector<pair<int,int>> pnt;
// void build(int a*){
//     root[0]= new node(0,new node(),new node());
//     for(int i=1;i<=n;i++) root[i]=root[i-1]->update(1,mxn,a[i]);
// }
int main() {
    cin >> n >> k;

    root1[0] = new node(PP, new node(), new node());

    root2[0] = new node(PP, new node(), new node());

   



    vector<pair<int,int>> vv;
    for(int i = 1; i <= n; i++) {
        int x,y;

        assert(scanf("%d %d",&x,&y));
        vv.emplace_back(y, x);
        pnt.emplace_back(x,y);
    }

    sort(pnt.begin(), pnt.end());
    pnt.insert(pnt.begin(), {0,0});

    sort(vv.begin(),vv.end());


    priority_queue< tuple<ll,int, int, int> > pq;




    for(int i = 1; i <= n; i++) {
        auto [x,y] = pnt[i];
        pos[i] = lower_bound(vv.begin(), vv.end(), make_pair(y, x)) - vv.begin() + 1;
        inv[pos[i]] = i;




        pii ed1 = root1[i - 1]-> query(1, n, pos[i], n);

        pii ed2 = root2[i - 1]-> query(1, n, 1, pos[i] - 1);


        pq.push({-(ed1.f + x - y), pos[i], ed1.s, 1});
        pq.push({-(ed2.f + x + y), pos[i], ed2.s, -1});

        // cout<<x<<" "<<y<<" "<<pos[i]<<" "<<ed1.s<<" "<<ed2.s<<" ==== "<<i<<endl;

        root1[i] = root1[i - 1]-> update(1, n, pos[i], y - x);
        root2[i] = root2[i - 1]-> update(1, n, pos[i], - y - x);

        

        id1[i] = i;
        id2[i] = i;


    }



    while(k--) {
        auto [dist, u, v, tp] = pq.top();
        pq.pop();
        dist = -dist;

        u = inv[u];
        v = inv[v];

        printf("%lld\n", dist);

        if(tp == 1) {
            root1[u] = root1[u]-> update(1, n, pos[v], inf);
            pii ed = root1[u]-> query(1, n, pos[u], n);

            auto [x,y] = pnt[u];
            pq.push({-(ed.f + x - y), pos[u], ed.s, 1});


        } else {
            root2[u] = root2[u]-> update(1, n, pos[v], inf);
            pii ed = root2[u]-> query(1, n, 1, pos[u] - 1);
            auto [x,y] = pnt[u];
            pq.push({-(ed.f + x + y), pos[u], ed.s, -1});

        }




    }


    
}

Compilation message (stderr)

road_construction.cpp: In constructor 'node::node(std::pair<long long int, int>, node*, node*)':
road_construction.cpp:13:9: warning: 'node::val' will be initialized after [-Wreorder]
   13 |     pii val;
      |         ^~~
road_construction.cpp:12:11: warning:   'node* node::left' [-Wreorder]
   12 |     node *left,*right;
      |           ^~~~
road_construction.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     node(pii _v = PP, node *l = NULL, node *r = NULL) : val(_v), left(l), right(r){};
      |     ^~~~
road_construction.cpp: In member function 'node* node::update(int, int, int, long long int)':
road_construction.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = l + r >> 1;
      |                   ~~^~~
road_construction.cpp: In member function 'std::pair<long long int, int> node::query(int, int, int, int)':
road_construction.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35