Submission #941430

#	Time	Username	Problem	Language	Result	Execution time	Memory
941430		tvladm2009	Road Construction (JOI21_road_construction)	C++14	5 / 100	10045 ms	218168 KiB

road_construction

#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int MAXN = 250228;
#define int ll

int n, k;
pair<ll, ll> z[MAXN];
map<ll, int> ind;
vector<ll> vals;
vector<int> occ[MAXN];

struct PST {
    struct Node {
        int result;
        Node* left;
        Node* right;

        Node (int val = 0) {
            result = val;
            left = right = NULL;
        }

        void refresh() {
            this->result = this->left->result + this->right->result;
        }
    };

    Node* build(int from, int to) {
        Node *node = new Node(0);
        if (from < to) {
            int mid = (from + to) / 2;
            node->left = build(from, mid);
            node->right = build(mid + 1, to);
        }
        return node;
    }

    Node* init(int n) {
        return build(1, n);
    }

    Node *update(Node *base, int from, int to, int x, int val) {
        if (from < to) {
            int mid = (from + to) / 2;
            Node* newNode = new Node();
            (*newNode) = (*base);
            if (x <= mid) {
                newNode->left = update(base->left, from, mid, x, val);
            } else {
                newNode->right = update(base->right, mid + 1, to, x, val);
            }
            newNode->refresh();
            return newNode;
        } else {
            return (new Node(base->result + val));
        }
    }
    
    int query(Node *node, int from, int to, int x, int y) {
        if (from == x && to == y) {
            return node->result;
        } else {
            int mid = (from + to) / 2;
            if (x <= mid && y <= mid) {
                return query(node->left, from, mid, x, y);
            } else if (mid + 1 <= x && mid + 1 <= y)  {
                return query(node->right, mid + 1, to, x, y);
            } else {
                return query(node->left, from, mid, x, mid) + query(node->right, mid + 1, to, mid + 1, y);
            }
        }
    }

    Node* version[MAXN];
    int n;

    void buildVersions(int nn) {
        n = nn;
        Node *partial = init(n);
        version[0] = partial;
        for (int i = 1; i <= n; i++) {
            for (auto pos: occ[i]) {
                partial = update(partial, 1, n, pos, +1);
            }
            version[i] = partial;
        }
    }

    int get(int when, int l, int r) {
        return query(version[when], 1, n, l, r);
    }
};

PST pst;

struct Query {
	ll l;
	ll r;
	ll x;	
	ll y;
};

ll getsmaller(ll x, ll ql, ll qr) {
    int l = 0, r = n - 1, when = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        if (vals[m] <= x) {
            when = ind[vals[m]];
            l = m + 1;
        } else {
            r = m - 1;
        }
    } 
    return pst.get(when, ql, qr);
}

ll get(ll m) {
	vector<Query> queries;
	for (int i = 0; i < n; i++) {
		int l = 0, r = i - 1, pos = i;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (z[i].first - z[mid].first <= m) {
				r = mid - 1;
				pos = mid;
			} else {
				l = mid + 1;
			}
		}
		queries.pb({pos, i - 1, z[i].second - m, z[i].second + m});
	}
	ll res = 0;
	for (auto it: queries) {
		ll l = it.l; 
		ll r = it.r;
		ll x = it.x;
		ll y = it.y; 
        l++;
        r++;
        if (l > r || l < 0) {
            continue;
        }
		res += getsmaller(y, l, r) - getsmaller(x - 1, l, r);
	}
	return res;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		z[i] = mp(x + y, x - y);
	}
	sort(z, z + n);
    {
        for (int i = 0; i < n; i++) {
            vals.pb(z[i].second);
        }
        sort(all(vals));
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (ind[vals[i]] == 0) {
                ind[vals[i]] = ++cnt;
            }
        }
        for (int i = 0; i < n; i++) {
             occ[ind[z[i].second]].pb(i + 1);
        }
    }  
    pst.buildVersions(n);
    ll l = 0, r = 4e9, val = 0;
	while (l <= r) {
		ll m = (l + r) / 2;
		if (get(m) >= k) {
			val = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}

    auto dist = [&](int i, int j) {
        return max(abs(z[i].first - z[j].first), abs(z[i].second - z[j].second));
    };
    
    vector<ll> sol;
    set<pair<ll, int>> s;
    int ptr = 0;
	for (int i = 0; i < n; i++) {
        s.insert(mp(z[i].second, i));
        while (ptr < i && z[i].first - z[ptr].first >= val) {
            s.erase(mp(z[ptr].second, ptr));
            ptr++;
        }
        auto it = s.find(mp(z[i].second, i));
        auto pos = it;
        while (pos != s.begin() && z[i].second - pos->first < val) {
            if (pos->second != i) {
                sol.pb(dist(pos->second, i));
            }
            pos--;
        }
        if (z[i].second - pos->first < val) {
            if (pos->second != i) {
                sol.pb(dist(pos->second, i));
            }
        }
        pos = it;
        while (pos != s.end() && pos->first - z[i].second < val) {
            if (pos->second != i) {
                sol.pb(dist(pos->second, i));
            }
            pos++;
        }
    }
    sort(all(sol));
    assert(sz(sol) <= k);
    while (sz(sol) < k) {
        sol.pb(val);
    }
    for (auto y: sol) {
        cout << y << '\n';
    }
    return 0;
}

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