oj.uz

Submission #392174

# Submission time Handle Problem Language Result Execution time Memory
392174 2021-04-20T15:25:00 Z limabeans Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 728228 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,ll> 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, (ll)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,ll> 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,ll>> 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, ll 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,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> 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,ll> ures = U[i+1].qryMin(1,1,N,loc+1,N);
	pair<ll,ll> 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);
	}
    };

    auto print = [&](priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq) {
	return;
	auto tmp = pq;
	while (tmp.size()) {
	    cout<<tmp.top().first<<","<<tmp.top().second<<endl;
	    tmp.pop();
	}
	cout<<endl;
    };

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

    print(pq);

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

	print(pq);
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 184040 KB Output is correct
2 Correct 850 ms 184176 KB Output is correct
3 Correct 691 ms 178348 KB Output is correct
4 Correct 628 ms 178156 KB Output is correct
5 Correct 872 ms 183012 KB Output is correct
6 Correct 42 ms 65356 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10116 ms 728228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1892 ms 711116 KB Output is correct
2 Correct 1840 ms 711124 KB Output is correct
3 Correct 40 ms 62916 KB Output is correct
4 Correct 1049 ms 711088 KB Output is correct
5 Correct 1421 ms 711216 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1892 ms 711116 KB Output is correct
2 Correct 1840 ms 711124 KB Output is correct
3 Correct 40 ms 62916 KB Output is correct
4 Correct 1049 ms 711088 KB Output is correct
5 Correct 1421 ms 711216 KB Output is correct
6 Correct 1875 ms 711168 KB Output is correct
7 Correct 1816 ms 711112 KB Output is correct
8 Correct 33 ms 62924 KB Output is correct
9 Correct 33 ms 62940 KB Output is correct
10 Correct 1833 ms 711108 KB Output is correct
11 Correct 1036 ms 711152 KB Output is correct
12 Correct 1387 ms 711040 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 184040 KB Output is correct
2 Correct 850 ms 184176 KB Output is correct
3 Correct 691 ms 178348 KB Output is correct
4 Correct 628 ms 178156 KB Output is correct
5 Correct 872 ms 183012 KB Output is correct
6 Correct 42 ms 65356 KB Output is correct
7 Execution timed out 10100 ms 366096 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 184040 KB Output is correct
2 Correct 850 ms 184176 KB Output is correct
3 Correct 691 ms 178348 KB Output is correct
4 Correct 628 ms 178156 KB Output is correct
5 Correct 872 ms 183012 KB Output is correct
6 Correct 42 ms 65356 KB Output is correct
7 Execution timed out 10116 ms 728228 KB Time limit exceeded
8 Halted 0 ms 0 KB -