oj.uz

Submission #392180

# Submission time Handle Problem Language Result Execution time Memory
392180 2021-04-20T15:29:44 Z limabeans Road Construction (JOI21_road_construction) C++17
100 / 100
 3249 ms 924900 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;
const ll inf = 1e18;

struct psegtree {
    pair<ll,int> pr; //(xyval, idx)
    psegtree *left;
    psegtree *right;

    psegtree() : pr(inf, -1), left(), right() {}

    static psegtree init(int dep) {
	if (dep==0) {
	    return {};
	} else {
	    psegtree *ch = new psegtree(init(dep-1));
	    return {ch, ch};
	}
    }


    psegtree(psegtree *l, psegtree *r) {
	left = l;
	right = r;
	pr = min(l->pr, r->pr);
    }

    psegtree upd(int v, int tl, int tr, int i, ll val) {
	//cout<<tl<<","<<tr<<": "<<left<<" "<<right<<endl;
	
	if (tl==tr) {
	    psegtree res;
	    res.pr = {val, i};
	    return res;
	} else {
	    int tm=(tl+tr)/2;
	    if (i<=tm) {
		return {new psegtree(left->upd(2*v,tl,tm,i,val)), right};
	    } else {
		return {left, new psegtree(right->upd(2*v+1,tm+1,tr,i,val))};
	    }
	}
    }

    pair<ll,int> qryMin(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return {inf, -1};
	} else if (l<=tl && tr<=r) {
	    return pr;
	} else {
	    int tm=(tl+tr)/2;
	    return min(left->qryMin(2*v,tl,tm,l,r), right->qryMin(2*v+1,tm+1,tr,l,r));
	}
    }
};

struct pt {
    ll x,y;
};

int n, k;
pt a[maxn];

psegtree U[maxn], D[maxn];



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    cin>>n>>k;
    for (int i=0; i<n; i++) {
	cin>>a[i].x>>a[i].y;
    }


    sort(a,a+n, [&](pt p, pt q) {
	return p.x<q.x;
    });
    

    vector<pair<ll,int>> ord;
    ord.push_back({-inf,-1}); // (y,i)
    for (int i=0; i<n; i++) {
	ord.push_back({a[i].y,i});
    }

    sort(ord.begin(), ord.end());
    int N = (int)ord.size() - 1;

    auto get = [&](ll y, int i) {
	return lower_bound(ord.begin(), ord.end(), make_pair(y,i)) - ord.begin();
    };

    U[0] = psegtree::init(19);
    D[0] = psegtree::init(19);


    // sort pts by x
    // each psegtree to the left contains active pts with lower x
    // within the psegtree, stuff is sorted by y, with value being (-x+y)



    
    for (int i=0; i<n; i++) {
	int loc = get(a[i].y, i);
	U[i+1] = U[i].upd(1,1,N,loc,-a[i].x+a[i].y);
	D[i+1] = D[i].upd(1,1,N,loc,-a[i].x-a[i].y);
    }


    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; // (ans, idx)



    // i is 0-indexed
    auto push = [&](int i) {
	ll x = a[i].x;
	ll y = a[i].y;
	int loc = get(y, i);
	pair<ll,int> ures = U[i+1].qryMin(1,1,N,loc+1,N);
	pair<ll,int> dres = D[i+1].qryMin(1,1,N,1,loc-1);

	if (ures.first == inf && dres.first == inf) {
	    return;
	}
	if (ures.first+x-y < dres.first+x+y) {
	    pq.push({ures.first+x-y, i});
	    U[i+1] = U[i+1].upd(1,1,N,ures.second, inf);
	} else {
	    pq.push({dres.first+x+y, i});
	    D[i+1] = D[i+1].upd(1,1,N,dres.second, inf);
	}
    };



    
    for (int i=0; i<n; i++) {
	push(i);
    }


    for (int it=0; it<k; it++) {
	auto cur = pq.top();
	pq.pop();
	cout<<cur.first<<"\n";
	push(cur.second);
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 184032 KB Output is correct
2 Correct 539 ms 184064 KB Output is correct
3 Correct 492 ms 178364 KB Output is correct
4 Correct 442 ms 178268 KB Output is correct
5 Correct 508 ms 182948 KB Output is correct
6 Correct 39 ms 65220 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2080 ms 919032 KB Output is correct
2 Correct 2021 ms 922168 KB Output is correct
3 Correct 367 ms 178172 KB Output is correct
4 Correct 1545 ms 921864 KB Output is correct
5 Correct 1524 ms 922004 KB Output is correct
6 Correct 1532 ms 922008 KB Output is correct
7 Correct 1666 ms 921412 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1805 ms 708020 KB Output is correct
2 Correct 1855 ms 708212 KB Output is correct
3 Correct 34 ms 62916 KB Output is correct
4 Correct 1065 ms 708000 KB Output is correct
5 Correct 1382 ms 708080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1805 ms 708020 KB Output is correct
2 Correct 1855 ms 708212 KB Output is correct
3 Correct 34 ms 62916 KB Output is correct
4 Correct 1065 ms 708000 KB Output is correct
5 Correct 1382 ms 708080 KB Output is correct
6 Correct 1824 ms 708192 KB Output is correct
7 Correct 1830 ms 707980 KB Output is correct
8 Correct 34 ms 62844 KB Output is correct
9 Correct 35 ms 62912 KB Output is correct
10 Correct 1852 ms 708076 KB Output is correct
11 Correct 1016 ms 707912 KB Output is correct
12 Correct 1400 ms 707980 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 184032 KB Output is correct
2 Correct 539 ms 184064 KB Output is correct
3 Correct 492 ms 178364 KB Output is correct
4 Correct 442 ms 178268 KB Output is correct
5 Correct 508 ms 182948 KB Output is correct
6 Correct 39 ms 65220 KB Output is correct
7 Correct 1859 ms 501728 KB Output is correct
8 Correct 1820 ms 502736 KB Output is correct
9 Correct 454 ms 178448 KB Output is correct
10 Correct 1313 ms 502360 KB Output is correct
11 Correct 1561 ms 501892 KB Output is correct
12 Correct 1028 ms 502688 KB Output is correct
13 Correct 1157 ms 501376 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 184032 KB Output is correct
2 Correct 539 ms 184064 KB Output is correct
3 Correct 492 ms 178364 KB Output is correct
4 Correct 442 ms 178268 KB Output is correct
5 Correct 508 ms 182948 KB Output is correct
6 Correct 39 ms 65220 KB Output is correct
7 Correct 2080 ms 919032 KB Output is correct
8 Correct 2021 ms 922168 KB Output is correct
9 Correct 367 ms 178172 KB Output is correct
10 Correct 1545 ms 921864 KB Output is correct
11 Correct 1524 ms 922004 KB Output is correct
12 Correct 1532 ms 922008 KB Output is correct
13 Correct 1666 ms 921412 KB Output is correct
14 Correct 1805 ms 708020 KB Output is correct
15 Correct 1855 ms 708212 KB Output is correct
16 Correct 34 ms 62916 KB Output is correct
17 Correct 1065 ms 708000 KB Output is correct
18 Correct 1382 ms 708080 KB Output is correct
19 Correct 1824 ms 708192 KB Output is correct
20 Correct 1830 ms 707980 KB Output is correct
21 Correct 34 ms 62844 KB Output is correct
22 Correct 35 ms 62912 KB Output is correct
23 Correct 1852 ms 708076 KB Output is correct
24 Correct 1016 ms 707912 KB Output is correct
25 Correct 1400 ms 707980 KB Output is correct
26 Correct 1859 ms 501728 KB Output is correct
27 Correct 1820 ms 502736 KB Output is correct
28 Correct 454 ms 178448 KB Output is correct
29 Correct 1313 ms 502360 KB Output is correct
30 Correct 1561 ms 501892 KB Output is correct
31 Correct 1028 ms 502688 KB Output is correct
32 Correct 1157 ms 501376 KB Output is correct
33 Correct 3151 ms 924864 KB Output is correct
34 Correct 3249 ms 924812 KB Output is correct
35 Correct 2497 ms 924160 KB Output is correct
36 Correct 1966 ms 924900 KB Output is correct
37 Correct 1940 ms 924848 KB Output is correct
38 Correct 2176 ms 923596 KB Output is correct