Submission #392368

#	Time	Username	Problem	Language	Result	Execution time	Memory
392368		ijxjdjd	Road Construction (JOI21_road_construction)	C++17	100 / 100	8568 ms	70324 KiB

road_construction

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
#define int ll

using namespace std;

using ll = long long;


const int MAXN = (int)(250000);
const int INF = (int)(1e9);;


struct point {
    int x, y;
};

int dist(point& x, point& y) {
    return abs(x.x-y.x)  + abs(x.y - y.y);
}
int SPLIT = 500;
signed main() {

	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, K;
	cin >> N >> K;
	if (N >= 200000) {
        SPLIT = 1250;
    }
	vector<point> vec(N);
	FR(i, N) {
        cin >> vec[i].x >> vec[i].y;
	}
    auto byX = [] (const point& lhs, const point& rhs) {
        return lhs.x < rhs.x;
    };
    auto byY = [] (const point& lhs, const point& rhs) {
        return lhs.y < rhs.y;
    };
	sort(all(vec), byX);
    list<point> cur;
    list<int> ans;
    int start = -1;
    for (int i = 0; i < N; i++) {
        cur.push_back(vec[i]);
        if ((i * (i+1))/2 >= K) {
            for (int j = 0; j <= i; j++) {
                for (int k = j+1; k <= i; k++) {
                    ans.push_back(dist(vec[j], vec[k]));
                }
            }
            cur.sort(byY);
            ans.sort();
            while (ans.size() > K) {
                ans.pop_back();
            }
            start = i+1;
            break;
        }
    }
    for (int i = start; i < N; i+=SPLIT) {
        list<int> mdist;
        if (cur.size() > 0) {
            auto it = cur.begin();
            while (it != cur.end()) {
                if ((*it).x <= vec[i].x - ans.back()) {
                    it = cur.erase(it);
                }
                else {
                    it++;
                }
            }
        }
        for (int j = i; j < min(N, i+SPLIT); j++) {
            for (int k = j+1; k < min(N, i+SPLIT); k++) {
                if (ans.back() > dist(vec[j], vec[k])) {
                    mdist.push_back(dist(vec[j], vec[k]));
                }
            }
        }
        sort(vec.begin() + i, min(vec.end(), vec.begin() + i + SPLIT), byY);
        if (cur.size() > 0) {
            auto l = cur.begin();
            auto r = cur.begin();
            for (int j = i; j < min(N, i+SPLIT); j++) {
                while (next(r) != cur.end() && (*next(r)).y - vec[j].y < ans.back()) {
                    r++;
                }
                while (l != cur.end() && vec[j].y - (*(l)).y >= ans.back()) {
                    l++;
                }
                for (auto it = l; it != next(r); it++) {
                    if (dist(*it, vec[j]) < ans.back()) {
                        mdist.push_back(dist(*it, vec[j]));
                    }
                }
            }
        }
        list<point> other;
        for (int j = i; j < min(N, i+SPLIT); j++) {
            other.push_back(vec[j]);
        }
        mdist.sort();
        cur.merge(other, byY);
        ans.merge(mdist);
        while (ans.size() > K) {
            ans.pop_back();
        }
    }
    for (auto it = ans.begin(); it != ans.end(); it++) {
        cout << *it << '\n';
    }
	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:56:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::list<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   56 |             while (ans.size() > K) {
      |                    ~~~~~~~~~~~^~~
road_construction.cpp:108:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::list<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  108 |         while (ans.size() > K) {
      |                ~~~~~~~~~~~^~~

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