oj.uz

Submission #392166

# Submission time Handle Problem Language Result Execution time Memory
392166 2021-04-20T15:19:31 Z limabeans Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 733028 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(20);
    D[0] = psegtree::init(20);


    // 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 838 ms 184076 KB Output is correct
2 Correct 844 ms 184152 KB Output is correct
3 Correct 698 ms 178376 KB Output is correct
4 Correct 608 ms 178204 KB Output is correct
5 Correct 808 ms 182980 KB Output is correct
6 Correct 40 ms 65348 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 716004 KB Output is correct
2 Correct 1820 ms 716104 KB Output is correct
3 Correct 34 ms 62924 KB Output is correct
4 Correct 1028 ms 713800 KB Output is correct
5 Correct 1380 ms 716384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 716004 KB Output is correct
2 Correct 1820 ms 716104 KB Output is correct
3 Correct 34 ms 62924 KB Output is correct
4 Correct 1028 ms 713800 KB Output is correct
5 Correct 1380 ms 716384 KB Output is correct
6 Correct 1809 ms 716024 KB Output is correct
7 Correct 1817 ms 716260 KB Output is correct
8 Correct 33 ms 62916 KB Output is correct
9 Correct 39 ms 62956 KB Output is correct
10 Correct 1947 ms 716100 KB Output is correct
11 Correct 1043 ms 713892 KB Output is correct
12 Correct 1396 ms 716384 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 184076 KB Output is correct
2 Correct 844 ms 184152 KB Output is correct
3 Correct 698 ms 178376 KB Output is correct
4 Correct 608 ms 178204 KB Output is correct
5 Correct 808 ms 182980 KB Output is correct
6 Correct 40 ms 65348 KB Output is correct
7 Execution timed out 10114 ms 367752 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 184076 KB Output is correct
2 Correct 844 ms 184152 KB Output is correct
3 Correct 698 ms 178376 KB Output is correct
4 Correct 608 ms 178204 KB Output is correct
5 Correct 808 ms 182980 KB Output is correct
6 Correct 40 ms 65348 KB Output is correct
7 Execution timed out 10126 ms 733028 KB Time limit exceeded
8 Halted 0 ms 0 KB -